Merge K Sorted Lists — Solution

Problem

You have k sorted linked lists and need to combine them into a single sorted linked list. Each input list is already sorted in ascending order — your job is to merge them all while preserving the sorted property.

For example, given three sorted lists:

[1,4,5]

[1,3,4]

[2,6]

• Input: lists = [[1,4,5],[1,3,4],[2,6]]
• Output: 1 → 1 → 2 → 3 → 4 → 4 → 5 → 6
• Explanation: All three lists interleaved in sorted order.

Intuition

At every step, you need the globally smallest unprocessed node, and that node always sits at the front of one of the lists (since each list is sorted). The challenge is doing this efficiently across k lists. A min-heap lets you always extract the current minimum in O(log k) time — far better than scanning all k fronts for every node. Alternatively, divide-and-conquer works by reducing the problem to repeated pairwise merges, which also achieves O(N log k) with less auxiliary space.

Approach 1 — Brute Force (Collect and Sort)

Traverse every node in every list, collect all values, sort them, then build a new linked list. Simple but wasteful — it ignores the fact that the lists are already sorted.

1. Walk all k lists and store every node value in an array.
2. Sort the array.
3. Build a new linked list from the sorted values using a dummy head.
4. Return the real head.

1def mergeKLists(lists):
2    all_values = []
3    for head in lists:
4        node = head
5        while node:
6            all_values.append(node.val)
7            node = node.next
8
9    all_values.sort()
10
11    dummy = ListNode(0)
12    current = dummy
13    for value in all_values:
14        current.next = ListNode(value)
15        current = current.next
16
17    return dummy.next

Time: O(N log N) where N is the total number of nodes — dominated by sorting all values together, discarding the sorted structure of each list.

Space: O(N) to store all values in the array, plus O(N) for the new list nodes.

Approach 2 — Min-Heap

Maintain a min-heap seeded with each list's head. Each pop gives the globally smallest current node; after adding it to the result, push that node's successor. The heap size never exceeds k.

1. Push the head of every non-null list into the min-heap (keyed by node value).
2. Create a dummy head for the output list.
3. While the heap is non-empty, pop the minimum node, link it to the result, and push its next if it exists.
4. Return dummy.next.

1import heapq
2
3def mergeKLists(lists):
4    min_heap = []
5
6    # Include list index as tiebreaker since Python can't compare ListNodes
7    for list_index, head in enumerate(lists):
8        if head:
9            heapq.heappush(min_heap, (head.val, list_index, head))
10
11    dummy = ListNode(0)
12    current = dummy
13
14    while min_heap:
15        value, list_index, node = heapq.heappop(min_heap)
16        current.next = node
17        current = current.next
18
19        if node.next:
20            heapq.heappush(min_heap, (node.next.val, list_index, node.next))
21
22    return dummy.next

Time: O(N log k) — each of the N total nodes is pushed and popped from a heap of size at most k, and each heap operation is O(log k).

Space: O(k) for the heap, which holds at most one node per list at any time; the result reuses the existing nodes rather than allocating new ones.

Approach 3 — Divide and Conquer

Repeatedly pair up adjacent lists and merge each pair, halving the number of lists per round. After O(log k) rounds, one merged list remains. This achieves the same time complexity as the heap but with only O(log k) call-stack space.

1. If the list array is empty, return null.
2. Set interval = 1; while interval < k, iterate through the array merging lists[i] with lists[i + interval], storing the result in lists[i].
3. Double interval after each pass.
4. Return lists[0].

1def mergeKLists(lists):
2    if not lists:
3        return None
4
5    def merge_two(list1, list2):
6        dummy = ListNode(0)
7        current = dummy
8        while list1 and list2:
9            if list1.val <= list2.val:
10                current.next = list1
11                list1 = list1.next
12            else:
13                current.next = list2
14                list2 = list2.next
15            current = current.next
16        # Attach the remaining non-empty list
17        current.next = list1 if list1 else list2
18        return dummy.next
19
20    interval = 1
21    k = len(lists)
22    while interval < k:
23        # Merge pairs that are `interval` apart
24        for i in range(0, k - interval, interval * 2):
25            lists[i] = merge_two(lists[i], lists[i + interval])
26        interval *= 2
27
28    return lists[0]

Time: O(N log k) — there are log k rounds; in each round, the total work across all pairs is O(N) since every node is touched once per round.

Space: O(log k) for the recursive call stack in mergeTwoLists, or effectively O(1) additional space when implemented iteratively as shown.

Complexity Summary

Common Mistakes

• Pushing ListNode directly into Python's heapq — when two nodes have equal values, Python tries to compare the nodes themselves and raises a TypeError. Fix: use a tuple (value, tiebreaker_index, node) so comparison never reaches the node.
• Skipping null-check before pushing to the heap — some lists may be empty or have null heads. Pushing None into the heap will cause a crash on the first comparison.
• Off-by-one in the divide-and-conquer loop bounds — the inner loop must check i < k - interval, not i < k, to ensure lists[i + interval] is always a valid index.
• Forgetting to advance the pointer after linking a node — in mergeTwoLists, after setting current.next = node, you must do current = current.next; omitting this creates an infinite loop as you keep rewiring the same tail.
• Returning lists[0] when lists is empty — always guard against an empty input array before indexing; return null immediately if lists has no elements.

Related Problems

• merge-two-sorted-lists — the two-list base case that mergeTwoLists implements internally
• sort-list — merge sort on a linked list applies the same divide-and-conquer pairwise-merge pattern
• kth-smallest-element-in-a-sorted-matrix — uses a min-heap to efficiently extract elements from k sorted sequences
• smallest-range-covering-elements-from-k-lists — same k-list heap approach, tracking the current window minimum and maximum
• find-k-closest-elements — heap-based extraction from sorted data, similar priority-queue reasoning