Merge k Sorted Lists

How it works

This is the same idea as divide and conquer, but done iteratively instead of using recursion.

We repeatedly merge the lists in pairs:

• In one pass:
  • Merge list 0 and list 1 -> get M0
  • Merge list 2 and list 3 -> get M1
  • Merge list 4 and list 5 -> get M2
  • ... and so on.
• After this pass, we have fewer lists (about half as many).
• Repeat this process on the new list of merged lists until only one list remains.

Each pairwise merge is just the usual merge of two sorted linked lists. By always merging lists two at a time, the total work is efficient and structured, similar to the merge step in merge sort.

Steps

1. If lists is empty, return null.
2. While the number of lists is greater than 1:
   • Create an empty list mergedLists.
   • Loop over lists in steps of 2:
     • Let l1 = lists[i].
     • Let l2 = lists[i + 1] if it exists, otherwise None.
     • Merge l1 and l2 using mergeList and append the result to mergedLists.
   • Set lists = mergedLists.
3. When the loop ends, lists[0] is the fully merged sorted list. Return it.

Merging two lists (mergeList(l1, l2)):

1. Create a dummy node and a tail pointer pointing to it.
2. While both l1 and l2 are non-empty:
   • Attach the smaller of l1 and l2 to tail.next.
   • Move the chosen list's pointer forward.
   • Move tail forward.
3. Attach any remaining nodes from l1 or l2 to tail.next.
4. Return dummy.next as the merged head.

Complexity

• Time complexity: O(n log k)
• Space complexity: O(k)

Where k is the total number of lists and n is the total number of nodes across k lists.

Things to watch for

Not Handling Empty Lists in the Input Array

The input array lists may contain null or empty linked lists. Failing to check for these before accessing node values will cause null pointer exceptions. Always verify that a list is non-empty before processing it.

Forgetting to Advance the Chosen List's Pointer

After selecting the smallest node from among the k lists, you must move that list's head pointer to the next node. Forgetting this step causes an infinite loop where the same node is repeatedly selected.

Incorrect Comparator for Min-Heap

When using a priority queue or min-heap, the comparator must compare node values correctly. In some languages, the default heap is a max-heap (like Python's heapq with negative values or C++'s priority_queue). Using the wrong comparison direction results in a max-heap instead of a min-heap, producing an incorrectly sorted output.

Not Using a Dummy Node for the Result List

Building the result list without a dummy head node requires special handling for the first node and complicates the logic. Using a dummy node simplifies the code by allowing uniform treatment of all nodes, then returning dummy.next as the result.

Modifying the Input Lists Array During Iteration

When merging lists one by one or in the divide-and-conquer approach, be careful about how you update the lists array. Overwriting elements while still iterating can lead to incorrect merges or skipped lists. Either use a separate array for merged results or iterate carefully with proper indexing.

from typing import List, Optional

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution:

    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        if not lists or len(lists) == 0:
            return None

        while len(lists) > 1:
            mergedLists = []
            for i in range(0, len(lists), 2):
                l1 = lists[i]
                l2 = lists[i + 1] if (i + 1) < len(lists) else None
                mergedLists.append(self.mergeList(l1, l2))
            lists = mergedLists
        return lists[0]

    def mergeList(self, l1, l2):
        dummy = ListNode()
        tail = dummy

        while l1 and l2:
            if l1.val < l2.val:
                tail.next = l1
                l1 = l1.next
            else:
                tail.next = l2
                l2 = l2.next
            tail = tail.next

        if l1:
            tail.next = l1
        if l2:
            tail.next = l2

        return dummy.next

/**
 * 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 {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if (lists.empty()) {
            return nullptr;
        }

        while (lists.size() > 1) {
            vector<ListNode*> mergedLists;
            for (int i = 0; i < lists.size(); i += 2) {
                ListNode* l1 = lists[i];
                ListNode* l2 = (i + 1) < lists.size() ? lists[i + 1] : nullptr;
                mergedLists.push_back(mergeList(l1, l2));
            }
            lists = mergedLists;
        }
        return lists[0];
    }

private:
    ListNode* mergeList(ListNode* l1, ListNode* l2) {
        ListNode dummy;
        ListNode* tail = &dummy;

        while (l1 && l2) {
            if (l1->val < l2->val) {
                tail->next = l1;
                l1 = l1->next;
            } else {
                tail->next = l2;
                l2 = l2->next;
            }
            tail = tail->next;
        }

        if (l1) {
            tail->next = l1;
        }
        if (l2) {
            tail->next = l2;
        }

        return dummy.next;
    }
};