Question for interview: combine two sorted, simply connected lists without creating new nodes

Question

This is a programming question asked during a written interview test. "You have two separately linked lists that are already sorted, you must combine them and return the head of the new list without creating any new additional nodes. The returned list must also be sorted."

Method signature: Node MergeLists (Node list1, Node list2);

Node below:

class Node{ int data; Node next; } 

I tried many solutions, but did not create extra Node hard drives. Please, help.

Here is the cover blog entry http://techieme.in/merging-two-sorted-singly-linked-list/

Answer 1

 Node MergeLists(Node list1, Node list2) { if (list1 == null) return list2; if (list2 == null) return list1; if (list1.data < list2.data) { list1.next = MergeLists(list1.next, list2); return list1; } else { list2.next = MergeLists(list2.next, list1); return list2; } } 

Answer 2

Recursion is not required so as not to allocate a new node:

 Node MergeLists(Node list1, Node list2) { if (list1 == null) return list2; if (list2 == null) return list1; Node head; if (list1.data < list2.data) { head = list1; } else { head = list2; list2 = list1; list1 = head; } while(list1.next != null) { if (list1.next.data > list2.data) { Node tmp = list1.next; list1.next = list2; list2 = tmp; } list1 = list1.next; } list1.next = list2; return head; } 

Answer 3

 Node MergeLists(Node node1, Node node2) { if(node1 == null) return node2; else (node2 == null) return node1; Node head; if(node1.data < node2.data) { head = node1; node1 = node1.next; else { head = node2; node2 = node2.next; } Node current = head; while((node1 != null) ||( node2 != null)) { if (node1 == null) { current.next = node2; return head; } else if (node2 == null) { current.next = node1; return head; } if (node1.data < node2.data) { current.next = node1; current = current.next; node1 = node1.next; } else { current.next = node2; current = current.next; node2 = node2.next; } } current.next = NULL // needed to complete the tail of the merged list return head; } 

Answer 4

Here is the algorithm for combining two sorted linked lists A and B:

 while A not empty or B not empty: if first element of A < first element of B: remove first element from A insert element into C end if else: remove first element from B insert element into C end while 

Here C will be the output list.

Answer 5

Look ma, no recursion!

 struct llist * llist_merge(struct llist *one, struct llist *two, int (*cmp)(struct llist *l, struct llist *r) ) { struct llist *result, **tail; for (result=NULL, tail = &result; one && two; tail = &(*tail)->next ) { if (cmp(one,two) <=0) { *tail = one; one=one->next; } else { *tail = two; two=two->next; } } *tail = one ? one: two; return result; } 

Answer 6

Iteration can be performed as shown below. Difficulty = O (n)

 public static LLNode mergeSortedListIteration(LLNode nodeA, LLNode nodeB) { LLNode mergedNode ; LLNode tempNode ; if (nodeA == null) { return nodeB; } if (nodeB == null) { return nodeA; } if ( nodeA.getData() < nodeB.getData()) { mergedNode = nodeA; nodeA = nodeA.getNext(); } else { mergedNode = nodeB; nodeB = nodeB.getNext(); } tempNode = mergedNode; while (nodeA != null && nodeB != null) { if ( nodeA.getData() < nodeB.getData()) { mergedNode.setNext(nodeA); nodeA = nodeA.getNext(); } else { mergedNode.setNext(nodeB); nodeB = nodeB.getNext(); } mergedNode = mergedNode.getNext(); } if (nodeA != null) { mergedNode.setNext(nodeA); } if (nodeB != null) { mergedNode.setNext(nodeB); } return tempNode; } 

Answer 7

 Node mergeList(Node h1, Node h2) { if (h1 == null) return h2; if (h2 == null) return h1; Node head; if (h1.data < h2.data) { head = h1; } else { head = h2; h2 = h1; h1 = head; } while (h1.next != null && h2 != null) { if (h1.next.data < h2.data) { h1 = h1.next; } else { Node afterh2 = h2.next; Node afterh1 = h1.next; h1.next = h2; h2.next = afterh1; if (h2.next != null) { h2 = afterh2; } } } return head; } 

Answer 8

A simple iterative solution.

 Node* MergeLists(Node* A, Node* B) { //handling the corner cases //if both lists are empty if(!A && !B) { cout << "List is empty" << endl; return 0; } //either of list is empty else if(!A) return B; else if(!B) return A; else { Node* head = NULL;//this will be the head of the newList Node* previous = NULL;//this will act as the /* In this algorithm we will keep the previous pointer that will point to the last node of the output list. And, as given we have A & B as pointer to the given lists. The algorithm will keep on going untill either one of the list become empty. Inside of the while loop, it will divide the algorithm in two parts: - First, if the head of the output list is not obtained yet - Second, if head is already there then we will just compare the values and keep appending to the 'previous' pointer. When one of the list become empty we will append the other 'left over' list to the output list. */ while(A && B) { if(!head) { if(A->data <= B->data) { head = A;//setting head of the output list to A previous = A; //initializing previous A = A->next; } else { head = B;//setting head of the output list to B previous = B;//initializing previous B = B->next; } } else//when head is already set { if(A->data <= B->data) { if(previous->next != A) previous->next = A; A = A->next;//Moved A forward but keeping B at the same position } else { if(previous->next != B) previous->next = B; B = B->next; //Moved B forward but keeping A at the same position } previous = previous->next;//Moving the Output list pointer forward } } //at the end either one of the list would finish //and we have to append the other list to the output list if(!A) previous->next = B; if(!B) previous->next = A; return head; //returning the head of the output list } } 

Answer 9

This can be done without creating an additional node, only with another Node link passing parameters (Node temp).

 private static Node mergeTwoLists(Node nodeList1, Node nodeList2, Node temp) { if(nodeList1 == null) return nodeList2; if(nodeList2 == null) return nodeList1; if(nodeList1.data <= nodeList2.data){ temp = nodeList1; temp.next = mergeTwoLists(nodeList1.next, nodeList2, temp); } else{ temp = nodeList2; temp.next = mergeTwoLists(nodeList1, nodeList2.next, temp); } return temp; } 

Answer 10

I would like to share how I thought about the solution ... I saw a solution that includes recursion, and they are quite amazing, is the result of well-functional and modular thinking. I really appreciate sharing.

I would like to add that recursion will not work for large strings, stack calls will overflow; so I decided to try an iterative approach ... and this is what I get.

The code is pretty straightforward, I added some inline comments to try and assure this.

If you don’t do this, let me know and I will improve readability (maybe I have a misleading interpretation of my own code).

 import java.util.Random; public class Solution { public static class Node<T extends Comparable<? super T>> implements Comparable<Node<T>> { T data; Node next; @Override public int compareTo(Node<T> otherNode) { return data.compareTo(otherNode.data); } @Override public String toString() { return ((data != null) ? data.toString() + ((next != null) ? "," + next.toString() : "") : "null"); } } public static Node merge(Node firstLeft, Node firstRight) { combine(firstLeft, firstRight); return Comparision.perform(firstLeft, firstRight).min; } private static void combine(Node leftNode, Node rightNode) { while (leftNode != null && rightNode != null) { // get comparision data about "current pair of nodes being analized". Comparision comparision = Comparision.perform(leftNode, rightNode); // stores references to the next nodes Node nextLeft = leftNode.next; Node nextRight = rightNode.next; // set the "next node" of the "minor node" between the "current pair of nodes being analized"... // ...to be equals the minor node between the "major node" and "the next one of the minor node" of the former comparision. comparision.min.next = Comparision.perform(comparision.max, comparision.min.next).min; if (comparision.min == leftNode) { leftNode = nextLeft; } else { rightNode = nextRight; } } } /** Stores references to two nodes viewed as one minimum and one maximum. The static factory method populates properly the instance being build */ private static class Comparision { private final Node min; private final Node max; private Comparision(Node min, Node max) { this.min = min; this.max = max; } private static Comparision perform(Node a, Node b) { Node min, max; if (a != null && b != null) { int comparision = a.compareTo(b); if (comparision <= 0) { min = a; max = b; } else { min = b; max = a; } } else { max = null; min = (a != null) ? a : b; } return new Comparision(min, max); } } // Test example.... public static void main(String args[]) { Node firstLeft = buildList(20); Node firstRight = buildList(40); Node firstBoth = merge(firstLeft, firstRight); System.out.println(firstBoth); } // someone need to write something like this i guess... public static Node buildList(int size) { Random r = new Random(); Node<Integer> first = new Node<>(); first.data = 0; first.next = null; Node<Integer> current = first; Integer last = first.data; for (int i = 1; i < size; i++) { Node<Integer> node = new Node<>(); node.data = last + r.nextInt(5); last = node.data; node.next = null; current.next = node; current = node; } return first; } 

}

Answer 11

Why are all these solutions so complex? You do not want to use recursion here because you can overdo it too much and throw an exception. Each solution uses too many lines of code or uses recursion. This is an extremely simple Java implementation with declarations and initializations already included.

  LinkedList<Integer> list1 = new LinkedList<Integer>(); LinkedList<Integer> list2 = new LinkedList<Integer>(); LinkedList<Integer> sortedList = new LinkedList<Integer>(); list1.add(1); list1.add(3); list1.add(5); list1.add(7); list1.add(9); list2.add(2); list2.add(4); list2.add(6); list2.add(8); list2.add(10); while (!list1.isEmpty() && !list2.isEmpty()) { Integer first1 = list1.getFirst(); Integer first2 = list2.getFirst(); if(first1 < first2) { sortedList.add(first1); list1.removeFirst(); } else if(first2 > first1) { sortedList.add(first2); list2.removeFirst(); } else // if first1 == first2 then default to first1 { sortedList.add(first1); list1.removeFirst(); } } for (Integer i : list1) // add any remaining values from list1 sortedList.add(i); for (Integer i : list2) // add any remaining values from list2 sortedList.add(i); for (Integer i : sortedList) // print the sorted list System.out.println(i); 

Prints: 1 2 3 4 5 6 7 8 9 10

Answer 12

An iterative solution is shown below. A recursive solution would be more compact, but since we do not know the length of the lists, recursion poses a risk.

The basic idea is similar to the merge step in a merge sort; we save a pointer corresponding to each input list; at each iteration, we move the pointer corresponding to the smaller element. However, there is one significant difference when most people stumble. In merge sorting, since we are using an array of results, the next insertion position is always the index of the result array. For a linked list we need to save a pointer to the last element of the sorted list. The pointer can move from one input list to another, depending on which one has the smaller item for the current iteration.

However, the following code is self-explanatory.

 public ListNode mergeTwoLists(ListNode l1, ListNode l2) { if (l1 == null) { return l2; } if (l2 == null) { return l1; } ListNode first = l1; ListNode second = l2; ListNode head = null; ListNode last = null; while (first != null && second != null) { if (first.val < second.val) { if (last != null) { last.next = first; } last = first; first = first.next; } else { if (last != null) { last.next = second; } last = second; second = second.next; } if (head == null) { head = last; } } if (first == null) { last.next = second; } if (second == null) { last.next = first; } return head; } 

Answer 13

First of all, understand the average value "without creating any new additional nodes . " As far as I understand, this does not mean that I do not have pointer (s) that points to existing node (s).

You cannot achieve this without pointing to pointers to existing nodes, even if you use recursion to achieve the same, the system will create pointers for you as call stacks. This is exactly the same as telling the system to add pointers that you avoided in your code.

A simple function to achieve the same using extra pointers :

 typedef struct _LLNode{ int value; struct _LLNode* next; }LLNode; LLNode* CombineSortedLists(LLNode* a,LLNode* b){ if(NULL == a){ return b; } if(NULL == b){ return a; } LLNode* root = NULL; if(a->value < b->value){ root = a; a = a->next; } else{ root = b; b = b->next; } LLNode* curr = root; while(1){ if(a->value < b->value){ curr->next = a; curr = a; a=a->next; if(NULL == a){ curr->next = b; break; } } else{ curr->next = b; curr = b; b=b->next; if(NULL == b){ curr->next = a; break; } } } return root; } 

Answer 14

 public static Node merge(Node h1, Node h2) { Node h3 = new Node(0); Node current = h3; boolean isH1Left = false; boolean isH2Left = false; while (h1 != null || h2 != null) { if (h1.data <= h2.data) { current.next = h1; h1 = h1.next; } else { current.next = h2; h2 = h2.next; } current = current.next; if (h2 == null && h1 != null) { isH1Left = true; break; } if (h1 == null && h2 != null) { isH2Left = true; break; } } if (isH1Left) { while (h1 != null) { current.next = h1; current = current.next; h1 = h1.next; } } if (isH2Left) { while (h2 != null) { current.next = h2; current = current.next; h2 = h2.next; } } h3 = h3.next; return h3; } 

Answer 15

 Node * merge_sort(Node *a, Node *b){ Node *result = NULL; if(a == NULL) return b; else if(b == NULL) return a; /* For the first node, we would set the result to either a or b */ if(a->data <= b->data){ result = a; /* Result next will point to smaller one in lists starting at a->next and b */ result->next = merge_sort(a->next,b); } else { result = b; /*Result next will point to smaller one in lists starting at a and b->next */ result->next = merge_sort(a,b->next); } return result; } 

Please refer to my blog post http://www.algorithmsandme.com/2013/10/linked-list-merge-two-sorted-linked.html

Answer 16

 Node MergeLists(Node list1, Node list2) { //if list is null return other list if(list1 == null) { return list2; } else if(list2 == null) { return list1; } else { Node head; //Take head pointer to the node which has smaller first data node if(list1.data < list2.data) { head = list1; list1 = list1.next; } else { head = list2; list2 = list2.next; } Node current = head; //loop till both list are not pointing to null while(list1 != null || list2 != null) { //if list1 is null, point rest of list2 by current pointer if(list1 == null){ current.next = list2; return head; } //if list2 is null, point rest of list1 by current pointer else if(list2 == null){ current.next = list1; return head; } //compare if list1 node data is smaller than list2 node data, list1 node will be //pointed by current pointer else if(list1.data < list2.data) { current.next = list1; current = current.next; list1 = list1.next; } else { current.next = list2; current = current.next; list2 = list2.next; } } return head; } } 

Answer 17

Here is a complete working example that uses a linked list implemented by java.util. You can simply copy the code below inside the main () method.

  LinkedList<Integer> dList1 = new LinkedList<Integer>(); LinkedList<Integer> dList2 = new LinkedList<Integer>(); LinkedList<Integer> dListMerged = new LinkedList<Integer>(); dList1.addLast(1); dList1.addLast(8); dList1.addLast(12); dList1.addLast(15); dList1.addLast(85); dList2.addLast(2); dList2.addLast(3); dList2.addLast(12); dList2.addLast(24); dList2.addLast(85); dList2.addLast(185); int i = 0; int y = 0; int dList1Size = dList1.size(); int dList2Size = dList2.size(); int list1Item = dList1.get(i); int list2Item = dList2.get(y); while (i < dList1Size || y < dList2Size) { if (i < dList1Size) { if (list1Item <= list2Item || y >= dList2Size) { dListMerged.addLast(list1Item); i++; if (i < dList1Size) { list1Item = dList1.get(i); } } } if (y < dList2Size) { if (list2Item <= list1Item || i >= dList1Size) { dListMerged.addLast(list2Item); y++; if (y < dList2Size) { list2Item = dList2.get(y); } } } } for(int x:dListMerged) { System.out.println(x); } 

Answer 18

Recursive path (Stefan's answer option)

  MergeList(Node nodeA, Node nodeB ){ if(nodeA==null){return nodeB}; if(nodeB==null){return nodeA}; if(nodeB.data<nodeA.data){ Node returnNode = MergeNode(nodeA,nodeB.next); nodeB.next = returnNode; retturn nodeB; }else{ Node returnNode = MergeNode(nodeA.next,nodeB); nodeA.next=returnNode; return nodeA; } 

Consider the list below to visualize this

2>4 list A 1>3 list B

Almost the same answer (not recursive) as Stefan, but with fewer comments / meaningful variable name. Also considered a double linked list in the comments if anyone is interested.

Let's look at an example.

5->10->15>21 // List1

2->3->6->20 //List2

 Node MergeLists(List list1, List list2) { if (list1 == null) return list2; if (list2 == null) return list1; if(list1.head.data>list2.head.data){ listB =list2; // loop over this list as its head is smaller listA =list1; } else { listA =list2; // loop over this list listB =list1; } listB.currentNode=listB.head; listA.currentNode=listA.head; while(listB.currentNode!=null){ if(listB.currentNode.data<listA.currentNode.data){ Node insertFromNode = listB.currentNode.prev; Node startingNode = listA.currentNode; Node temp = inserFromNode.next; inserFromNode.next = startingNode; startingNode.next=temp; startingNode.next.prev= startingNode; // for doubly linked list startingNode.prev=inserFromNode; // for doubly linked list listB.currentNode= listB.currentNode.next; listA.currentNode= listA.currentNode.next; } else { listB.currentNode= listB.currentNode.next; } } 

Answer 19

Take the question as below:

pseudo code:

 Compare the two heads A and B. If A <= B, then add A and move the head of A to the next node. Similarly, if B < A, then add B and move the head of B to the next node B. If both A and B are NULL then stop and return. If either of them is NULL, then traverse the non null head till it becomes NULL. 

the code:

 public Node mergeLists(Node headA, Node headB) { Node merge = null; // If we have reached the end, then stop. while (headA != null || headB != null) { // if B is null then keep appending A, else check if value of A is lesser or equal than B if (headB == null || (headA != null && headA.data <= headB.data)) { // Add the new node, handle addition separately in a new method. merge = add(merge, headA.data); // Since A is <= B, Move head of A to next node headA = headA.next; // if A is null then keep appending B, else check if value of B is lesser than A } else if (headA == null || (headB != null && headB.data < headA.data)) { // Add the new node, handle addition separately in a new method. merge = add(merge, headB.data); // Since B is < A, Move head of B to next node headB = headB.next; } } return merge; } public Node add(Node head, int data) { Node end = new Node(data); if (head == null) { return end; } Node curr = head; while (curr.next != null) { curr = curr.next; } curr.next = end; return head; } 

Answer 20

  /* Simple/Elegant Iterative approach in Java*/ private static LinkedList mergeLists(LinkedList list1, LinkedList list2) { Node head1 = list1.start; Node head2 = list2.start; if (list1.size == 0) return list2; if (list2.size == 0) return list1; LinkedList mergeList = new LinkedList(); while (head1 != null && head2 != null) { if (head1.getData() < head2.getData()) { int data = head1.getData(); mergeList.insert(data); head1 = head1.getNext(); } else { int data = head2.getData(); mergeList.insert(data); head2 = head2.getNext(); } } while (head1 != null) { int data = head1.getData(); mergeList.insert(data); head1 = head1.getNext(); } while (head2 != null) { int data = head2.getData(); mergeList.insert(data); head2 = head2.getNext(); } return mergeList; } /* Build-In singly LinkedList class in Java*/ class LinkedList { Node start; int size = 0; void insert(int data) { if (start == null) start = new Node(data); else { Node temp = start; while (temp.getNext() != null) { temp = temp.getNext(); } temp.setNext(new Node(data)); } size++; } @Override public String toString() { String str = ""; Node temp=start; while (temp != null) { str += temp.getData() + "-->"; temp = temp.getNext(); } return str; } } 

Answer 21

 LLNode *mergeSorted(LLNode *h1, LLNode *h2) { LLNode *h3=NULL; LLNode *h3l; if(h1==NULL && h2==NULL) return NULL; if(h1==NULL) return h2; if(h2==NULL) return h1; if(h1->data<h2->data) { h3=h1; h1=h1->next; } else { h3=h2; h2=h2->next; } LLNode *oh=h3; while(h1!=NULL && h2!=NULL) { if(h1->data<h2->data) { h3->next=h1; h3=h3->next; h1=h1->next; } else { h3->next=h2; h3=h3->next; h2=h2->next; } } if(h1==NULL) h3->next=h2; if(h2==NULL) h3->next=h1; return oh; } 

Answer 22

 // Common code for insert at the end private void insertEnd(int data) { Node newNode = new Node(data); if (head == null) { newNode.next = head; head = tail = newNode; return; } Node tempNode = tail; tempNode.next = newNode; tail = newNode; } private void mergerTwoSortedListInAscOrder(Node tempNode1, Node tempNode2) { if (tempNode1 == null && tempNode2 == null) return; if (tempNode1 == null) { head3 = tempNode2; return; } if (tempNode2 == null) { head3 = tempNode1; return; } while (tempNode1 != null && tempNode2 != null) { if (tempNode1.mData < tempNode2.mData) { insertEndForHead3(tempNode1.mData); tempNode1 = tempNode1.next; } else if (tempNode1.mData > tempNode2.mData) { insertEndForHead3(tempNode2.mData); tempNode2 = tempNode2.next; } else { insertEndForHead3(tempNode1.mData); insertEndForHead3(tempNode2.mData); tempNode1 = tempNode1.next; tempNode2 = tempNode2.next; } } if (tempNode1 != null) { while (tempNode1 != null) { insertEndForHead3(tempNode1.mData); tempNode1 = tempNode1.next; } } if (tempNode2 != null) { while (tempNode2 != null) { insertEndForHead3(tempNode2.mData); tempNode2 = tempNode2.next; } } } 

:) GlbMP

Answer 23

In the beginning, I created only one dummy node to save myself from many “if” conditions.

  public ListNode mergeTwoLists(ListNode l1, ListNode l2) { ListNode list1Cursor = l1; ListNode list2Cursor = l2; ListNode currentNode = new ListNode(-1); // Dummy node ListNode head = currentNode; while (list1Cursor != null && list2Cursor != null) { if (list1Cursor.val < list2Cursor.val) { currentNode.next = list1Cursor; list1Cursor = list1Cursor.next; currentNode = currentNode.next; } else { currentNode.next = list2Cursor; list2Cursor = list2Cursor.next; currentNode = currentNode.next; } } // Complete the rest while (list1Cursor != null) { currentNode.next = list1Cursor; currentNode = currentNode.next; list1Cursor = list1Cursor.next; } while (list2Cursor != null) { currentNode.next = list2Cursor; currentNode = currentNode.next; list2Cursor = list2Cursor.next; } return head.next; } 

Answer 24

 public Node NewMerge(Node head1, Node head2) { if (head1 != null && head2 != null) { if (head1.data > head2.data) { head2.next = NewMerge(head1, head2.next); return head2; } else if (head1.data == head2.data) { head1.next = NewMerge(head1.next, head2.next); return head1; } else { head1.next = NewMerge(head1.next, head2); return head1; } } else if (head1 == null) return head2; else return head1; } 

I tried to run it in the Console application, after I initialized two NodeList that contain more than 6400 nodes, I found that my console application throws a StackOverflowException. Does anyone have a similar problem?

Answer 25

 private static Node mergeLists(Node L1, Node L2) { Node P1 = L1.val < L2.val ? L1 : L2; Node P2 = L1.val < L2.val ? L2 : L1; Node BigListHead = P1; Node tempNode = null; while (P1 != null && P2 != null) { if (P1.next != null && P1.next.val >P2.val) { tempNode = P1.next; P1.next = P2; P1 = P2; P2 = tempNode; } else if(P1.next != null) P1 = P1.next; else { P1.next = P2; break; } } return BigListHead; } 

Answer 26

 void printLL(){ NodeLL cur = head; if(cur.getNext() == null){ System.out.println("LL is emplty"); }else{ //System.out.println("printing Node"); while(cur.getNext() != null){ cur = cur.getNext(); System.out.print(cur.getData()+ " "); } } System.out.println(); } void mergeSortedList(NodeLL node1, NodeLL node2){ NodeLL cur1 = node1.getNext(); NodeLL cur2 = node2.getNext(); NodeLL cur = head; if(cur1 == null){ cur = node2; } if(cur2 == null){ cur = node1; } while(cur1 != null && cur2 != null){ if(cur1.getData() <= cur2.getData()){ cur.setNext(cur1); cur1 = cur1.getNext(); } else{ cur.setNext(cur2); cur2 = cur2.getNext(); } cur = cur.getNext(); } while(cur1 != null){ cur.setNext(cur1); cur1 = cur1.getNext(); cur = cur.getNext(); } while(cur2 != null){ cur.setNext(cur2); cur2 = cur2.getNext(); cur = cur.getNext(); } printLL(); } 

Answer 27

Here is the code on how to combine the two sorted linked lists headA and headB:

 Node* MergeLists1(Node *headA, Node* headB) { Node *p = headA; Node *q = headB; Node *result = NULL; Node *pp = NULL; Node *qq = NULL; Node *head = NULL; int value1 = 0; int value2 = 0; if((headA == NULL) && (headB == NULL)) { return NULL; } if(headA==NULL) { return headB; } else if(headB==NULL) { return headA; } else { while((p != NULL) || (q != NULL)) { if((p != NULL) && (q != NULL)) { int value1 = p->data; int value2 = q->data; if(value1 <= value2) { pp = p->next; p->next = NULL; if(result == NULL) { head = result = p; } else { result->next = p; result = p; } p = pp; } else { qq = q->next; q->next = NULL; if(result == NULL) { head = result = q; } else { result->next = q; result = q; } q = qq; } } else { if(p != NULL) { pp = p->next; p->next = NULL; result->next = p; result = p; p = pp; } if(q != NULL) { qq = q->next; q->next = NULL; result->next = q; result = q; q = qq; } } } } return head; }