CareerCup

So, the lists must be sorted.

struct List{
   int v;
   List* n;
};

//Suppose the List has a header
List* merge(List* a, List* b){
    List head;
    List* c=&head;
    List* iterA=null, iterB=null;
    c->v=-1;
    c->n=null;
    iterA=a->n;
    terB=b->n;
    while(iterA!=null&&iterB!=null){
        if(iterA->v > iterB->v){
            c->n = iterB;
            c = iterB;
            iterB = iterB->n;
        }
        else{
            c->n = iterA;
            c = iterA;
            iterA = iterA->n;
        }
    }
    if(iterA == null){
        c->n = iterB;
    }
    else{
        c->n = iterA;
    }
    free(a); //free the header
    free(b); //free the header
}

geeksforgeeks.org/?p=7740

merge_sort(List* a)
{
M=a->count();
l=new List (m/2)
l=copy_list(a,m/2+1,m);
r=copy_list(a, 0,m/2);
merge_sort(l);
merge_sort(r);
list = merge (l,r);
}

copy_list(List *a)
{
List *b;
while (a!=null)
{
b.data=a.data;
b=b.next
a=a.next;
}
}

node *merge(node *one, node *two) {
node *curr, *temp1 = one, *temp2 = two, *prev = NULL, *ret;
one->data > two->data ? ret = two : ret = one;
while(temp1 || temp2) {
if(temp1 && (temp2 == NULL || temp1->data <= temp2->data)) {
curr = temp1;
temp1 = temp1->next;
} else if (temp2) {
curr = temp2;
temp2 = temp2->next;
}
prev ? prev->next = curr:0;
prev = curr;
}
return ret;
}

The below is a java program to merge sort a linked list. It works!
time complexity - O(n logn)
space complexity - O(1)

class MergeSortForLinkedList{
	private static int linkedListLength;
	private static LinkedListNode mainList;

        //this method needs to be called to merge the linked list
	public static LinkedListNode mergeSort(LinkedListNode list){
		if(list == null)
			return null;
		linkedListLength = findListLength(list); //finds length of linked list
		mainList = list;
		return mergeSort(0, linkedListLength-1);
	}
	
	private static LinkedListNode mergeSort(int start, int end){
		if(start == end){
			LinkedListNode x = mainList;
			mainList = mainList.nextNode;
			x.nextNode = null;
			return x;
		}
		int mid = (start+end)/2;
		LinkedListNode left = mergeSort(start,mid);
		LinkedListNode right = mergeSort(mid+1, end);
		LinkedListNode toReturn = merge(left, right);
		return toReturn;
	}
	//merges two null ended linked lists in natural order and returns the head of the resultant list
	private static LinkedListNode merge(LinkedListNode list1, LinkedListNode list2){
		if(list1 == null)
			return list2;
		if(list2 == null)
			return list1;
		LinkedListNode head;
		if( list1.data <= list2.data ){
			head = list1;
			list1 = list1.nextNode;
		}
		else{
			head = list2;
			list2 = list2.nextNode;
		}
		LinkedListNode tail = head;
		while(list1 != null && list2!=null){
			if( list1.data <= list2.data){
				tail.nextNode = list1;
				tail = list1;
				list1 = list1.nextNode;
			}
			else{
				tail.nextNode = list2;
				tail = list2;
				list2 = list2.nextNode;
			}
		
		}
		if(list1 == null && list2 == null)
			return head;
		if(list1 == null){
			tail.nextNode = list2;
			return head;
		}
		if(list2 == null){
			tail.nextNode = list1;
			return head;
		}
		return null;
	}
	
	private static int findListLength(LinkedListNode head){
		if(head == null)
			return 0;
		int length = 0;
		while(head != null){
			length++;
			head = head.nextNode;
		}
		return length;
	
	}
	public static void printLinkedList(LinkedListNode head){
		if(head == null)
			return;
		while(head != null){
			System.out.print(head.data+" ");
			head = head.nextNode;
		}
		System.out.println();
		return;
	}

	public static void main(String[] args){
		LinkedListNode node1 = new LinkedListNode(3, null);
		LinkedListNode head = node1;
		LinkedListNode node2 = new LinkedListNode(5, null);
		node1.nextNode = node2;
		node1 = new LinkedListNode(1, null);
		node2.nextNode = node1;
		node2 = new LinkedListNode(2, null);
		node1.nextNode = node2;
		node1 = new LinkedListNode(0, null);
		node2.nextNode = node1;
		node2 = new LinkedListNode(3, null);
		node1.nextNode = node2;
		node1 = new LinkedListNode(7, null);
		node2.nextNode = node1;
		node2 = new LinkedListNode(8, null);
		node1.nextNode = node2;
		
		printLinkedList(head);
		LinkedListNode sortedListHead = mergeSort(head);
		printLinkedList(sortedListHead);	
		return;
	}
}

Output:

new-users-macbook:Interviews newuser$ java MergeSortForLinkedList
3 5 1 2 0 3 7 8
0 1 2 3 3 5 7 8