Merge k Sorted Lists — InterviewPrepKit

Solving tips

The next output node is the min of k current heads; a size-k min-heap gives it in O(log k) for O(N log k) total, beating the O(N*k) all-heads scan.
In Python push tuples (val, index, node) since ListNodes aren't comparable; the unique index breaks value ties before the comparison reaches the node.
Alternative same-bound approach: divide-and-conquer pairwise merging (merge lists 1&2, 3&4, ...) halves the count each round for log k rounds, O(1) extra space.
Avoid folding lists one-at-a-time into an accumulator (O(N*k), re-walks early nodes); handle empty lists and lists = [] as real test cases.

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. Total node count across all lists is what matters for performance — call it N. Merging two sorted lists is a classic easy problem; the point here is doing it for k lists without paying more than necessary.

Examples

Input: lists = [[1, 4, 5], [1, 3, 4], [2, 6]] → Output: [1, 1, 2, 3, 4, 4, 5, 6] All eight nodes interleaved into one ascending list.
Input: lists = [] → Output: [] No lists at all — the result is empty.
Input: lists = [[], [0]] → Output: [0] Empty lists contribute nothing and must not crash anything.

Constraints

k is in [0, 10^4], each list has up to 500 nodes, total N up to about 5 * 10^5 in practice.
-10^4 <= Node.val <= 10^4; each input list is sorted ascending.
The bound that matters: with k up to 10^4, an O(N * k) approach (comparing 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

class Solution:
    def mergeKLists(self, 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). It actually runs fast in CPython, but it throws away the sortedness of the inputs — the interview is testing whether you can beat log N with log k, and the O(N) scratch array plus all-new nodes defeat the purpose of relinking a linked list.

Approach 2 — Min-heap of current heads

The insight: 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 aren’t comparable — so push (val, index, node) where 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

class Solution:
    def mergeKLists(self, 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 exhausted), 5, 6 — output [1, 1, 2, 3, 4, 4, 5, 6], and the heap never held more than 3 entries.

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

Approach 3 — Divide and conquer: merge in pairs

The insight: merging lists into an accumulator one at a time is O(N * k), because the early nodes get re-walked in every one of the k merges. Balance the work instead — merge pairs, then pairs of the merged results — and each node participates in only log k merges. This is the same divide-and-conquer shape as merge sort’s combine phase, done iteratively over the array of lists.

# 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

class Solution:
    def mergeKLists(self, 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 = self.mergeTwo(lists[i], lists[i + interval])
                lists[i] = merged
            interval *= 2
        return lists[0]

    def mergeTwo(self, 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

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]. 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 will try node1 < node2 on a value tie and raise TypeError; the (val, index, node) tuple’s unique index 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 = [] itself.
The tempting one-at-a-time merge. Folding each list into a growing result looks like reuse of easy Merge Two Lists, but is 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 exactly one candidate per source in a size-k min-heap and pay log k per element instead of log N or k. And whenever you fold k things together, remember that 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.