CareerCup

They say it is list so we do not need extra memory will not be needed till you can merge the nodes in between by using next pointers

something like this : may need to be fixed for bugs\cornercase but logic should be like this
public static MergedList MergeLists(LinkList<LinkList<int>> sortedAllLists)
{
LinkList<int> MergedList = sortedAdjencyList.take(1);
foreach(List<int> outerlist in sortedList.skip(1).take())
{
MergeList(MergedList, outerList);
}

return MergedList;
}

public void MergeList(LinkList list1, LinkList list2)
{
if(list1.data < list2.data)
{
list root = list1current = list1;
}

while(list1current != null && list2current != null)
{
if(list1current < list2current)
list1current = list2current++;
else
{
temp = list1current.next ;
list1current.next = list2current;
list2current = list2current.next;
list1current.next.next = temp;
list1current = list1current.next;
}
}

if (list2current != null)
{
list1current.next = list2current;
}

return rootlist;
}

You can merge the lists in pairs. First merge lists 1 and 2, then 3 and 4, and so on. After you're done, you have half as many lists. Make another pass to merge those lists in pairs again and you'll have a quarter of the number of lists you started with. Do this again and again until you only have one list.

Over the course of the entire algorithm, the number of comparisons is O(log N * totalInputElements), since it's one comparison per element per pass. One pass halves the number of lists and therefore there will be O(log N) passes. This number of comparisons is the asymptotic minimum for merging N sorted lists. Only O(1) space is used (additional space would be used if you were doing this with arrays, but it's not needed for linked lists).

Glue the lists together into a single list.
Mergesort the list (can be done with O(1) space for LLs)

We have N Lists. Maintain a min heap of size N. The heap will store the top value of all the lists initially and will help in getting the min at any point of time in O(1). Each node in the heap will also store a reference to the list it belongs to, inorder to handle duplicates. Have N pointers pointing to the top of the N lists. Do the same thing merge sort does, but get the min in O(logN) time instead of doing O(N) comparisons.