Leetcode #11: ‘Merge K Sorted Lists’

Hello everyone. Today, let’s solve the Leetcode problem ‘Merge K Sorted Lists’, Given k sorted lists, the task is to merge them into a single sorted list. In this article, we will discuss a Divide and Conquer approach to efficiently solve this problem.

Problem:

We are given an array of k linked-lists lists, each linked list is sorted in ascending order and we need to

Merge all the linked-lists into one sorted linked-list and return it.

Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
Explanation: The linked-lists are:
[
  1->4->5,
  1->3->4,
  2->6
]
merging them into one sorted list:
1->1->2->3->4->4->5->6

Approach

The Divide and Conquer approach is an efficient technique to solve the problem. The idea is to repeatedly divide the given k lists into smaller subproblems until we have only two lists left. Then, we merge these two lists using a merging subroutine and continue this process until we obtain a single sorted list.

Here is a step-by-step overview of the approach:

1. If the number of lists is 0, return NULL as there are no lists to merge.
2. If there is only one list, return that list as the merged result.
3. Divide the k lists into two halves.
4. Recursively merge the first half of the lists.
5. Recursively merge the second half of the lists.
6. Merge the two merged lists obtained from steps 4 and 5 into a single sorted list.

To merge two lists, we compare the values of the nodes in the two lists and select the smaller value at each step. We continue this process until we reach the end of either list and then append the remaining nodes from the non-empty list to the merged list.

Here is C++ Code to implement it :

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */

class Solution {
    ListNode *merge(vector<ListNode*>& lists,int left,int right)
    {
        if(left==right)     //Only 1 list, therefore can't be merged
            return lists[left];
        
        int k = right-left+1;   //No of current lists
        ListNode *head,*h1,*h2,*ptr;
        head = h1 = h2 = NULL;
        h1 = merge(lists,left,left+k/2-1);    //Merge 1st half and store its head in h1
        h2 = merge(lists,left+k/2,right); //Merge 2nd half and store its head in h2
        
        //Merge h1 and h2 into head
        if(!h1 and !h2) //No list is present
            return head;
        else if(!h1)    //Only the 2nd list is present
            return h2;
        else if(!h2)    //Only the 1st list is present
            return h1;
        
        if(!h1 or (h1 and h1->val>h2->val))
        {   head = h2;  h2=h2->next;    }
        else
        {   head = h1;  h1=h1->next;    }
        
        ptr = head;
        while(h1 or h2)
        {
            if(!h1)
            {   ptr->next = h2;   h2=h2->next;  ptr=ptr->next;  }
            else if(!h2)
            {   ptr->next = h1;   h1=h1->next;  ptr=ptr->next;  }
            else if(h1->val < h2->val)
            {   ptr->next=h1;   h1=h1->next;    ptr=ptr->next;  }
            else
            {   ptr->next=h2;   h2=h2->next;    ptr=ptr->next;  }
        }
        return head;
    }
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        int k = lists.size();
        if(k==0)
            return NULL;
        else if(k==1)
            return lists[0];
        ListNode *head,*h1,*h2,*ptr;
        head = h1 = h2 = NULL;
        h1 = merge(lists,0,k/2);    //Merge 1st half
        if(k/2+1 <= k-1)
            h2 = merge(lists,k/2+1,k-1);    //Merge 2nd half
        
        //Merge h1 and h2 into head
        if(!h1 and !h2) //No list is present
            return head;
        else if(!h1)    //Only the 2nd list is present
            return h2;  
        else if(!h2)    //Only the 1st list is present
            return h1;
        
        if(!h1 or (h1 and h1->val>h2->val))
        {   head = h2;  h2=h2->next;    }
        else
        {   head = h1;  h1=h1->next;    }
        
        ptr = head;
        while(h1 or h2)
        {
            if(!h1)
            {   ptr->next = h2;   h2=h2->next;  ptr=ptr->next;  }
            else if(!h2)
            {   ptr->next = h1;   h1=h1->next;  ptr=ptr->next;  }
            else if(h1->val < h2->val)
            {   ptr->next=h1;   h1=h1->next;    ptr=ptr->next;  }
            else
            {   ptr->next=h2;   h2=h2->next;    ptr=ptr->next;  }
        }
        return head;
    }
};

Time Complexity

The time complexity of the above approach can be analyzed as follows:

Let’s assume n is the total number of nodes across all k lists.

• In each recursive call, we divide the number of lists into two halves. Hence, the number of recursive calls is O(log k).
• In each recursive call, we merge two lists of size n by comparing the values of their nodes. This takes O(n) time.
• Therefore, the overall time complexity can be expressed as O(n log k).

Space Complexity

The space complexity of the above approach can be analyzed as follows:

• In each recursive call, we create two new lists, h1 and h2, to store the merged lists of the first and second halves, respectively. The size of these lists is at most n/2.
• The maximum number of recursive calls is O(log k).
• Therefore, the overall space complexity can be expressed as O(n log k), considering the space used by the recursive call stack and the merged lists.

Conclusion

In this article, we discussed a Divide and Conquer approach to merge k-sorted lists efficiently. By recursively dividing the lists into smaller subproblems and merging them using a merging subroutine, we can obtain the final sorted list.

Thank you for reading.

— Shruti Mandaokar

https://www.linkedin.com/in/shruti-mandaokar/