DAY 104 - Merge k Sorted Lists

Hey Guys!, Welcome to DAY 104 and we are continuing on our journey to master linked list. Today we are back with a hard interesting question. So Let's get right down to it.

Question: Merge k Sorted Lists

You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.

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

Examples:

Example 1:

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

Example 2:

Input: lists = []
Output: []

Question Breakdown:

• Ok so despite it being tagged as the hard problem is quite easy to understand.
• The description is asking us to make an merge all the given linked lists in a vector which are already sorted in order.
• So what we have to do is basically merge all the lists but If the size is too big, we can't be declaring pointers for every list right.

The Approach

To solve this problem efficiently, we can use a divide-and-conquer strategy. Here's a step-by-step explanation of our approach:

1. Handle Edge Cases:

   • If the input array of linked lists is empty, we return nullptr, indicating an empty list.
   • If there's only one linked list in the array, we return it as the result.

2. Pairwise Merge:

   • We start by dividing the array of linked lists into pairs and merging each pair into a single list.
   • For example, if we have k linked lists, we pair the first list with the (k/2 + 1)-th list, the second list with the (k/2 + 2)-th list, and so on.
   • We do this merging iteratively until we have only one merged list remaining.

3. Merging Two Lists:

   • To merge two sorted linked lists, we use a helper function called mergeTwoLists.
   • This function takes two pointers, p1 and p2, each pointing to the head of a sorted list.
   • We create a new dummy node, ans, to build the merged list.
   • While both p1 and p2 are not null, we compare the values at their current positions.
   • We append the node with the smaller value to the merged list and advance the respective pointer.
   • We continue this process until one of the lists becomes null.
   • Finally, we attach the remaining nodes (if any) from the non-null list to the merged list.

4. Return the Result:

   • After pairwise merging, we're left with one merged list in the array.
   • We return the head of this merged list as our final result.

Code:

    ListNode* mergeTwoLists(ListNode* p1, ListNode* p2){
        ListNode* ans = new ListNode();
        ListNode* temp = ans;

        while(p1 && p2){
            if(p1->val < p2->val){
                temp->next = p1;
                p1 = p1->next;
            }
            else{
                temp->next= p2;
                p2 = p2->next;
            }
            temp = temp->next;
        }

        if(p1) temp->next = p1;
        else temp->next = p2;

        return ans->next;

    }
   ListNode* mergeKLists(vector<ListNode*>& lists) {
    int n = lists.size();
    if (n == 0) return nullptr;
    if (n == 1) return lists[0];

    while (n > 1) {
        int k = (n + 1) / 2;
        for (int i = 0; i < n / 2; ++i) {
            lists[i] = mergeTwoLists(lists[i], lists[i + k]);
        }
        n = k;
    }

    return lists[0];
}

Let's analyze the time and space complexity of our solution:

• Time Complexity: The time complexity depends on the number of nodes in all the linked lists. During each pairwise merge, we traverse all the nodes exactly once. Since we perform log₂(k) iterations (where k is the number of linked lists), the total time complexity is O(N⋅log(k)), where N is the total number of nodes.

• Space Complexity: The space complexity is O(1) for variables used in the algorithm, and we don't use any additional data structures apart from the input and output. Therefore, the space complexity is O(1).