Merge k Sorted Lists — InterviewPrepKit

Problem

You are given an array of k linked lists, each already sorted in ascending order. Combine all of them into a single sorted linked list and return its head.

Some of the k lists may be empty, and the array itself may be empty. Let N be the total number of nodes across all lists; performance is measured against N. Merging two sorted lists is straightforward; the challenge is merging k of them efficiently.

Examples

Input: lists = [[1, 4, 5], [1, 3, 4], [2, 6]] → Output: [1, 1, 2, 3, 4, 4, 5, 6] All eight nodes merged into one ascending list.
Input: lists = [] → Output: [] No input lists, so the result is empty.
Input: lists = [[], [0]] → Output: [0] Empty lists must be handled without error.

Constraints

k is in [0, 10^4], each list has up to 500 nodes, total N up to about 5 * 10^5.
-10^4 <= Node.val <= 10^4; each input list is sorted ascending.
With k up to 10^4, an O(N * k) approach (scanning all k heads for every output node, or merging lists into the result one at a time) is too slow. The target is O(N log k).

Think about it first

Hint 1

At every step, the next output node is the smallest among the current heads of the k lists. How do you repeatedly extract the minimum of k changing candidates faster than scanning all k each time?

Hint 2

A min-heap of size k gives you the smallest head in O(log k). Pop a node, append it to the output, and push that node's successor — every node enters and leaves the heap exactly once.

Hint 3

Alternative with the same O(N log k) bound and O(1) heap-free space: divide and conquer. Merge lists in pairs (1 with 2, 3 with 4, …), halving the count each round; after log k rounds one list remains, and each round touches every node once.

TL;DR

Min-heap of the k current heads, or divide-and-conquer pairwise merging — both O(N log k) time; heap uses O(k) space, pairwise merging O(1) (plus O(log k) if done recursively).

Approach 1 — Brute force: collect every value and sort

Ignore that the lists are sorted: dump all N values into one array, sort it, and build a fresh list.

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

def mergeKLists(lists: List[Optional[ListNode]]) -> Optional[ListNode]:
    vals = []
    for node in lists:
        while node:
            vals.append(node.val)
            node = node.next
    vals.sort()
    dummy = ListNode()
    tail = dummy
    for v in vals:
        tail.next = ListNode(v)
        tail = tail.next
    return dummy.next

Time O(N log N), space O(N). This runs fast in CPython, but it ignores the sortedness of the inputs. The interview is testing whether you can replace log N with log k, and the O(N) scratch array plus all-new nodes defeats the point of relinking an existing linked list.

Approach 2 — Min-heap of current heads

The next node of the answer is always the minimum of at most k candidates: the current head of each list. A binary min-heap (a priority queue that pops its smallest element in O(log size)) maintains exactly that candidate set. Pop the smallest, append it to the output, push its successor. Every node passes through the heap once.

Python’s heapq compares tuples element by element, and ListNodes are not comparable, so push (val, index, node). The list index breaks value ties before the comparison ever reaches the node.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
import heapq
from typing import List, Optional

def mergeKLists(lists: List[Optional[ListNode]]) -> Optional[ListNode]:
    heap = []
    for i, node in enumerate(lists):
        if node:
            heapq.heappush(heap, (node.val, i, node))
    dummy = ListNode()
    tail = dummy
    while heap:
        _, i, node = heapq.heappop(heap)
        tail.next = node
        tail = node
        if node.next:
            heapq.heappush(heap, (node.next.val, i, node.next))
    return dummy.next

Walkthrough on [[1, 4, 5], [1, 3, 4], [2, 6]]: the heap starts as {(1,0), (1,1), (2,2)} (value, list). Pop (1, list 0) → output [1], push its successor 4. Pop (1, list 1) → [1, 1], push 3. Pop (2, list 2) → [1, 1, 2], push 6. Then 3 (push 4), 4 from list 0 (push 5), 4 from list 1 (its list is now exhausted), 5, 6, giving [1, 1, 2, 3, 4, 4, 5, 6]. The heap never held more than 3 entries.

Time O(N log k): N pops and at most N pushes on a heap of size at most k. Space O(k) for the heap; nodes are relinked, not copied.

Approach 3 — Divide and conquer: merge in pairs

Merging lists into a single accumulator one at a time is O(N * k), because the early nodes are re-walked in every one of the k merges. Balance the work instead: merge pairs, then pairs of the merged results. Each node then participates in only log k merges. This is the same structure as merge sort’s combine phase, applied iteratively over the array of lists.

flowchart TD
    A["list 0: 1 4 5"] --> M1["merge"]
    B["list 1: 1 3 4"] --> M1
    C["list 2: 2 6"] --> M2["merge"]
    M1 --> R1["1 1 3 4 4 5"] --> M2
    M2 --> R2["1 1 2 3 4 4 5 6"]

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

def mergeTwo(l1: Optional[ListNode],
             l2: Optional[ListNode]) -> Optional[ListNode]:
    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
    tail.next = l1 if l1 else l2
    return dummy.next


def mergeKLists(lists: List[Optional[ListNode]]) -> Optional[ListNode]:
    if not lists:
        return None
    interval = 1
    while interval < len(lists):
        for i in range(0, len(lists) - interval, interval * 2):
            merged = mergeTwo(lists[i], lists[i + interval])
            lists[i] = merged
        interval *= 2
    return lists[0]

Walkthrough on [[1, 4, 5], [1, 3, 4], [2, 6]]: round 1 (interval = 1) merges list 0 with list 1 → [1, 1, 3, 4, 4, 5]; list 2 has no partner and waits. Round 2 (interval = 2) merges that result with [2, 6] → [1, 1, 2, 3, 4, 4, 5, 6]. That is two rounds, ceil(log2 3), each touching every live node once.

Time O(N log k): log k rounds, O(N) total merge work per round. Space O(1), pointers only. The recursive formulation of the same idea costs O(log k) stack.

Common pitfalls

Pushing bare nodes into the heap. heapq tries node1 < node2 on a value tie and raises TypeError. The unique index in the (val, index, node) tuple guarantees the comparison never reaches the nodes.
Skipping empty lists. Both the initial heap build and mergeTwo must tolerate None heads. lists = [[], [0]] is a real test case, as is lists = [].
The one-at-a-time merge. Folding each list into a growing result reuses Merge Two Lists but costs O(N * k): the accumulator’s early nodes are re-traversed in every merge. Pair up instead.
Off-by-one in the pairing loop. The range bound len(lists) - interval ensures i + interval is a valid partner. Getting it wrong either drops the odd list out or indexes past the end.

Pattern takeaway

“Repeatedly take the minimum of k moving fronts” is a heap problem: keep one candidate per source in a size-k min-heap and pay log k per element instead of k. And whenever you fold k things together, sequential folding re-processes early elements k times while balanced pairwise folding processes everything only log k times, the same reason merge sort beats insertion sort.