CareerCup

Does the new list has to be sorted as well ? Can u give an example ?

first n elements sorted, so increment ptr n/2 places and sort the next n elements. Then do the same thing until whole list sorted. (m/n) * nlogn = mlogn runtime assuming m = total num elements across all lists.

Lets say each list is of size M
Take list[0],list[1] merge them, take list[2],list[3] merge them,.. take list[n-2],list[n-1] and merge them
Next take two previously sorted list and merge them, keep doing this unil there is one list remaining.
compleixty O(MXN)

or

Merge the list[0] and list[1] call the merged list mergeList
for(i = 2 ; i < n ;i++)
merge(mergeList, list[i])
This is again a O(MXN) algo

struct node{
	node * next;
	int data;

};

node * simple_merge(node * list1, node * list2)
{	
	node * result = NULL;
	node * p1 = list1;
	node * p2 = list2;
	node * p3 = NULL;
	while(p1!=NULL && p2!=NULL)
	{
		node * chosen = NULL;
		if(p2== NULL|| (p1!=NULL && p2->data > p1->data))
		{
			chosen = p1;
			p1 = p1->next;
		}
		else
		{
			chosen = p2;
			p2 = p2->next;
		}
		
		if(result == NULL)
		{
			result = chosen;
			p3 = result;
		}
		else
		{
			p3->next = chosen;
			p3 = chosen;
		}
		chosen->next = NULL;
		
		
		
	}
	return result;
}

node * merge_lists(node ** lists, int numLists)
{
	node * result = NULL;
	node ** currents = new node * [numLists];
	if(numLists == 1)
	{
		result = lists[0];
	}
	if(numLists == 2)
	{
		result=simple_merge(lists[0], lists[1]);
	}
	else
	{
		int index = numLists/2;
		node * result1= merge_lists(lists, index);
		node * result2 = merge_lists(lists[index+1], numLists-index);
		result=simple_merge(result1, result2);
	}
	return result;

}

public static Node NmergeSort(LinkedList A[]){
int N= A.length;
Node res=null;
Node node = new Node(null, 0);
while(A.length>0){
int min = Integer.MAX_VALUE;
int I=-1;
for(int i=0;i<N;i++){
if(A[i]!=null && A[i].head.val<min){
min = A[i].head.val;
I=i;
}
}
node = A[I].head;
A[I].head = A[I].head.next;
if(res==null){
res = node;
}else{
node.next=res;
res=node;
}
}
return res;
}

public static Node NmergeSort(LinkedList A[]){
int N= A.length;
Node res=null;
Node node = new Node(null, 0);
while(A.length>0){
int min = Integer.MAX_VALUE;
int I=-1;
for(int i=0;i<N;i++){
if(A[i]!=null && A[i].head.val<min){
min = A[i].head.val;
I=i;
}
}
node = A[I].head;
A[I].head = A[I].head.next;
if(res==null){
res = node;
}else{
node.next=res;
res=node;
}
}
return res;
}