Merge K Sorted Lists - Leetcode Solution

Problem Statement: 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.

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

Constraints:

• k == lists.length
• 0 <= k <= 10^4
• 0 <= lists[i].length <= 500
• -10^4 <= lists[i][j] <= 10^4
• lists[i] is sorted in ascending order.
• The sum of lists[i].length won't exceed 10^4.

Solution: Approach 1: Brute Force

The brute force solution is quite straightforward. We can store all the nodes of all the linked lists in an array, and then sort the array. Finally, we can construct a new sorted linked list and iterate through the sorted array to add each node into the new list.

The time complexity of this approach is O(NlogN) where N is the total number of nodes in all the k linked lists. Sorting N nodes takes O(NlogN), and iterating N nodes to construct the final linked list takes O(N).

Algorithm:

1. Create a new empty array.
2. Traverse each of the k linked lists, and store all the nodes in the new array.
3. Sort the new array in ascending order.
4. Create a new empty linked list.
5. Traverse the sorted array, and add each node to the new linked list.
6. Return the new linked list.

Code:

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        vector<int> nodes;
        
        // store all the nodes of all the linked lists in an array
        for (auto& head : lists) {
            for (ListNode* p = head; p != nullptr; p = p->next) {
                nodes.push_back(p->val);
            }
        }
        
        // sort the array in ascending order
        sort(nodes.begin(), nodes.end());
        
        // construct a new sorted linked list
        ListNode dummy;
        ListNode* tail = &dummy;
        for (auto val : nodes) {
            tail->next = new ListNode(val);
            tail = tail->next;
        }
        
        return dummy.next;
    }
};

Approach 2: Divide and Conquer

The brute force solution is inefficient because it sorts the nodes in all the linked lists. A more efficient approach is to use a divide-and-conquer technique. We can merge pairs of linked lists repeatedly until there is only one linked list left.

Algorithm:

1. Divide the k linked lists into two halves. (If k is odd, the second half should be larger than the first half.)
2. Recursively merge the two halves into two sorted linked lists.
3. Recursively merge the two sorted linked lists into one sorted linked list.

Code:

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if (lists.empty()) return nullptr;
        int k = lists.size();
        while (k > 1) {
            int mid = (k + 1) / 2;
            for (int i = 0; i < k / 2; ++i) {
                lists[i] = mergeTwoLists(lists[i], lists[i + mid]);
            }
            k = mid;
        }
        return lists[0];
    }
    
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode dummy;
        ListNode* tail = &dummy;
        while (l1 != nullptr && l2 != nullptr) {
            if (l1->val < l2->val) {
                tail->next = l1;
                l1 = l1->next;
            } else {
                tail->next = l2;
                l2 = l2->next;
            }
            tail = tail->next;
        }
        if (l1 != nullptr) tail->next = l1;
        if (l2 != nullptr) tail->next = l2;
        return dummy.next;
    }
};

1