Merge K Sorted Linked Lists

Difficulty Level Hard
Frequently asked in Adobe Amazon Apple Bloomberg ByteDance Databricks eBay Facebook Goldman Sachs Microsoft Oracle Palantir Technologies Twitter Uber Wish
Divide and Conquer Heap Linked-ListViews 1794

Merge K sorted linked lists problem is so famous as per the interview point of view. This question asks so many times in big companies like Google, Microsoft, Amazon, etc.  As the name suggests we’ve been provided with k sorted linked lists. We have to merge them together into a Single Sorted Linked List.

Let’s look into a sample test case to understand it better:

Example

Input

[

1->2->3,

1->4->6,

2->3

]

Output

1->1->2->2->3->3->4->6

Approach-1 for Merge K Sorted Linked Lists

Brute Force 

  • Traverse all the linked lists and put all the values in an Array/ArrayList/Vector(Whatever storage you find convenient)
  • Sort the data
  • Create a new linked list from the sorted data

Voila!our merged and sorted linked list is ready. Let’s understand that better by a code.

Java Program

class Solution 
{
    public ListNode mergeKLists(ListNode[] lists) 
    {
        ListNode aux=new ListNode(0);
        List<Integer>lisa=new ArrayList<Integer>();
        for(int i=0;i<lists.length;i++)
        {
            ListNode ptr=lists[i];
            while(ptr!=null)
            {
                lisa.add(ptr.val);
                ptr=ptr.next;
            }
        }
        Collections.sort(lisa);
        ListNode ptr=aux;
        for(int i=0;i<lisa.size();i++)
        {
            ListNode temp=new ListNode(lisa.get(i));
            temp.next=null;
            ptr.next=temp;
            ptr=ptr.next;
        }
        return aux.next;
    }
}

C++ Program

class Solution 
{
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) 
    {
    vector<int>store;
    for(int i=0;i<lists.size();i++)
        {
            ListNode *ptr=lists[i];
            while(ptr!=NULL)
            {
                store.push_back(ptr->val);
                ptr=ptr->next;
            }
        }
        sort(store.begin(),store.end());
        ListNode *ptr=new ListNode();
        ListNode *aux=ptr;
        for(int i=0;i<store.size();i++)
        {
            ListNode *temp=new ListNode(store[i]);
            temp->next=NULL;
            ptr->next=temp;
            ptr=ptr->next;
        }
        return aux->next;
    }
};
[

1->2->3,

1->4->6,

2->3

]
1->1->2->2->3->3->4->6

Complexity Analysis

Let us now look into the time complexity of the above solution:

The time is taken for traversal and creation: O(n)

The time is taken for sorting: O(n log n)

Making the time complexity: O(n log n)

Approach-2 for Merge K Sorted Linked Lists

Using Min-Heap

A Priority Queue can be used as a storage

Advantages:

  • No need for sorting

Let’s look into the same with the help of a code

Java Program

class Solution 
{
    public ListNode mergeKLists(ListNode[] lists)
    {
    Queue<Integer>store=new PriorityQueue();
    for(int i=0;i<lists.length;i++)
    {
        ListNode ptr=lists[i];
        while(ptr!=null)
        {
            store.add(ptr.val);
            ptr=ptr.next;
        }
    }
    if(store.isEmpty() )    
        return null;
    ListNode head=new ListNode(store.poll());
    ListNode cur=head;
    while(!store.isEmpty())
    {
        ListNode temp=new ListNode(store.poll());
        cur.next=temp;
        cur=cur.next;
    }
    return head;
    }
}
[
2->5->7->9,
1->2->3->->10
]
1->2->2->3->5->7->9->10

Complexity Analysis

The time complexity of the above: O(n log n)

Approach-3 for Merge K Sorted Linked Lists

Divide and Conquer

  • The Divide step

OBJECTIVE-Sends k lists to merge function k/2 at time

  • The Merge step

OBJECTIVE-To consider smaller values and add them to create a new list

    • Create a pointer to return the combined list
    • Add the smaller value from either list
    • Increment pointer from which value has been taken
    • Return merged and sorted linked list from two lists
Merge K Sorted Linked Lists
Showing a merge for a few lists

Let’s understand that better with the help of code

Java Program

class Solution 
{
    public static ListNode merge(ListNode l1,ListNode l2)
    {
        if(l1==null)
            return l2;
        if(l2==null)
            return l1;
        ListNode aux=new ListNode();
        ListNode head=aux;
        while(l1!=null && l2!=null)
        {
            if(l1.val>l2.val)
            {
                aux.next=l2;
                l2=l2.next;
            }
            else 
            {
                aux.next=l1;
                l1=l1.next;
            }
            aux=aux.next;
        }
        if(l1!=null)
            aux.next=l1;
        else if(l2!=null)
            aux.next=l2;
        return head.next;
    }
    public static ListNode divide(ListNode[]lists,int start,int end)
    {
        if(end<start)
            return null;
        if(end==start)
            return lists[start];
        int mid=start+(end-start)/2;
        return(merge(divide(lists,start,mid),divide(lists,mid+1,end)));
    }
    public ListNode mergeKLists(ListNode[] lists)
    {
     if(lists == null) 
         return null;
     if(lists.length == 1) 
         return lists[0];
     return divide(lists,0,lists.length-1);   
    }
}

C++ Program

class Solution 
{
  public:
    ListNode* merge(ListNode *l1,ListNode *l2)
    {
        if(l1==NULL)
            return l2;
        if(l2==NULL)
            return l1;
        ListNode *aux=new ListNode();
        ListNode *head=aux;
        while(l1!=NULL && l2!=NULL)
        {
            if(l1->val>l2->val)
            {
                aux->next=l2;
                l2=l2->next;
            }
            else 
            {
                aux->next=l1;
                l1=l1->next;
            }
            aux=aux->next;
        }
        if(l1!=NULL)
            aux->next=l1;
        else if(l2!=NULL)
            aux->next=l2;
        return head->next;
    }
    public:
    ListNode* divide(vector<ListNode*>&lists,int start,int end)
    {
        if(end<start)
            return NULL;
        if(end==start)
            return lists[start];
        int mid=start+(end-start)/2;
        return(merge(divide(lists,start,mid),divide(lists,mid+1,end)));
    }
    public:
    ListNode* mergeKLists(vector<ListNode*>& lists) 
    {
     if(lists.size() == 0) 
         return NULL;
     if(lists.size() == 1) 
         return lists[0];
     return divide(lists,0,lists.size()-1);   
    }
};
[
1->2,
3,
4->5->6->7,
8->9->10,
11
]
1->2->3->4->5->6->7->8->9->10->11

Complexity Analysis

The time complexity=O(n log n)

The space complexity=O(1)

References

Translate »