Problem Statement

You are given k sorted linked lists, each with n1, n2,.., nk nodes respectively. Your task is to merge these linked list into one sorted linked list and return the head of the final list.

Examples

Example 1:

Input: k = 3
       lists = [
                1->4->5,
                1->3->4,
                2->6
               ]
Output: 1->1->2->3->4->4->5->6

Explanation: All the linked lists are merged into a single sorted list.

Different Approaches

1️⃣ Brute Force Approach

Collect all nodes from the k linked list to a vector. Sort the vector. Reconstruct the new Linked list from the sorted vector.

Approach:

1. Traverse each list and store all nodes in a vector.
2. Sort the vector based on the node values.
3. Create a new linked list from the sorted vector.

Code:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}                    // Default constructor initializing val to 0 and next to nullptr
 *     ListNode(int x) : val(x), next(nullptr) {}               // Constructor initializing val to x and next to nullptr
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}  // Constructor initializing val to x and setting next to the provided pointer
 * };
 */

class Solution {
public:
    // Function to merge k sorted linked lists into a single sorted linked list
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        vector<int> container; // A vector to store all values from the k linked lists
        
        // Step 1: Traverse through each linked list in the input vector
        for (int i = 0; i < lists.size(); i++) {
            ListNode* head = lists[i]; // Get the head of the current linked list
            while (head != nullptr) { // Iterate through the nodes of the linked list
                container.push_back(head->val); // Store the value of the current node in the vector
                head = head->next; // Move to the next node
            }
        }
        
        // Step 2: Sort the collected values in ascending order
        sort(container.begin(), container.end());
        
        // Step 3: Create a new linked list from the sorted values
        ListNode* result = new ListNode(0); // Dummy node to simplify list construction
        ListNode* current = result; // Pointer to the current node in the new linked list
        
        for (int i = 0; i < container.size(); i++) {
            current->next = new ListNode(container[i]); // Create a new node with the current value and link it
            current = current->next; // Move to the newly created node
        }
        
        // Return the head of the newly constructed linked list (skip the dummy node)
        return result->next;
    }
};

Complexity Analysis:

• Time Complexity: O(n) + O(n log n) + O(n)
  • O(n): Collecting values to a vector.
  • O(n log n): Sorting the vector.
  • O(n): Constructing the new linked list.
• Space Complexity: O(n) + O(n)
  • O(n): For the vector.
  • O(n): For new linked list.

2️⃣ Min-Heap (Priority Queue)

Intuition:

• Use a min-heap to always fetch the smallest node across k lists.
• Continuously add the smallest node to the result and push its next node to the heap.

Approach:

1. Push the head of each linked list into a min-heap.
2. Extract the smallest node from the heap, append it to the result, and push its next node into the heap.
3. Repeat until the heap is empty.

Code:

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

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

// Min-heap comparator
struct compare {
    bool operator()(ListNode* a, ListNode* b) {
        return a->val > b->val; // Min-heap: smallest value at the top
    }
};

ListNode* mergeKLists(vector<ListNode*>& lists) {
    priority_queue<ListNode*, vector<ListNode*>, compare> minHeap;

    // Push the head of each linked list into the heap
    for (auto list : lists) {
        if (list) minHeap.push(list);
    }

    // Dummy node to start the result list
    ListNode dummy(0);
    ListNode* tail = &dummy;

    // Merge nodes
    while (!minHeap.empty()) {
        ListNode* smallest = minHeap.top();
        minHeap.pop();

        tail->next = smallest; // Append smallest node to result
        tail = tail->next;

        if (smallest->next) {
            minHeap.push(smallest->next);
        }
    }

    return dummy.next;
}

3️⃣ Divide and Conquer (Optimal)

Intuition:

• Pairwise merge the lists recursively, similar to the merge step in merge sort.
• Divide the k lists into halves until there's only one list in each subset.
• Merge each subset.

Steps:

1. If there's only one list, return it.
2. Divide the k lists into two halves and recursively merge each half.
3. Use the "merge two sorted lists" function to merge the results.

Code:

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    if (!l1) return l2;
    if (!l2) return l1;

    if (l1->val < l2->val) {
        l1->next = mergeTwoLists(l1->next, l2);
        return l1;
    } else {
        l2->next = mergeTwoLists(l1, l2->next);
        return l2;
    }
}

ListNode* mergeKLists(vector<ListNode*>& lists, int left, int right) {
    if (left > right) return nullptr;
    if (left == right) return lists[left];

    int mid = left + (right - left) / 2;
    ListNode* l1 = mergeKLists(lists, left, mid);
    ListNode* l2 = mergeKLists(lists, mid + 1, right);

    return mergeTwoLists(l1, l2);
}

ListNode* mergeKLists(vector<ListNode*>& lists) {
    if (lists.empty()) return nullptr;
    return mergeKLists(lists, 0, lists.size() - 1);
}