# Merge k Sorted Lists

- **Canonical ID**: `merge-k-sorted-lists`
- **Canonical URL**: https://dsacheatsheet.com/problems/merge-k-sorted-lists
- **Difficulty**: hard
- **Patterns**: Linked Lists, Heaps
- **Version**: 1.0.0 (verified 2026-11-11T21:15:00Z)
- **Original Problem**: https://leetcode.com/problems/merge-k-sorted-lists/

## 1. Core Invariant / The Trick

Either push the head of each non-empty list into a size-k min-heap (`O(N log k)` time, `O(k)` space) OR pairwise divide-and-conquer merge halves (`O(N log k)` time, `O(1)` extra heap allocations).

## 2. Complexity Bounds & Proof

- **Time Complexity**: `O(N log k)`
- **Space Complexity**: `O(1)`
- **Proof**: Bottom-up pairwise merging halves k lists per round across log k rounds touching all N total nodes once per round.

## 3. Minimal Idiomatic Code

### Python
```python
def mergeKLists(lists: list[Optional[ListNode]]) -> Optional[ListNode]:
    if not lists:
        return None
    def merge2(a, b):
        dummy = tail = ListNode()
        while a and b:
            if a.val <= b.val:
                tail.next, a = a, a.next
            else:
                tail.next, b = b, b.next
            tail = tail.next
        tail.next = a or b
        return dummy.next
    step = 1
    while step < len(lists):
        for i in range(0, len(lists) - step, step * 2):
            lists[i] = merge2(lists[i], lists[i + step])
        step *= 2
    return lists[0]
```

### TypeScript
```typescript
export function mergeKLists(lists: Array<ListNode | null>): ListNode | null {
  if (!lists.length) return null;
  const merge2 = (a: ListNode | null, b: ListNode | null): ListNode | null => {
    const dummy = new ListNode(0);
    let tail = dummy;
    while (a && b) {
      if (a.val <= b.val) { tail.next = a; a = a.next; }
      else { tail.next = b; b = b.next; }
      tail = tail.next;
    }
    tail.next = a ?? b;
    return dummy.next;
  };
  for (let step = 1; step < lists.length; step *= 2) {
    for (let i = 0; i + step < lists.length; i += step * 2) {
      lists[i] = merge2(lists[i], lists[i + step]);
    }
  }
  return lists[0];
}
```

### C++
```cpp
ListNode* mergeKLists(vector<ListNode*>& lists) {
    auto cmp = [](ListNode* a, ListNode* b) { return a->val > b->val; };
    priority_queue<ListNode*, vector<ListNode*>, decltype(cmp)> pq(cmp);
    for (auto* l : lists) if (l) pq.push(l);
    ListNode dummy(0), *tail = &dummy;
    while (!pq.empty()) {
        auto* cur = pq.top(); pq.pop();
        tail->next = cur; tail = tail->next;
        if (cur->next) pq.push(cur->next);
    }
    return dummy.next;
}
```

### Java
```java
ListNode mergeKLists(ListNode[] lists) {
    PriorityQueue<ListNode> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a.val));
    for (ListNode l : lists) if (l != null) pq.add(l);
    ListNode dummy = new ListNode(0), tail = dummy;
    while (!pq.isEmpty()) {
        ListNode cur = pq.poll();
        tail.next = cur; tail = tail.next;
        if (cur.next != null) pq.add(cur.next);
    }
    return dummy.next;
}
```

### Go
```go
func mergeKLists(lists []*ListNode) *ListNode {
    if len(lists) == 0 { return nil }
    for step := 1; step < len(lists); step *= 2 {
        for i := 0; i+step < len(lists); i += step * 2 {
            lists[i] = mergeTwoLists(lists[i], lists[i+step])
        }
    }
    return lists[0]
}
```

## 4. Failure Modes & Interview Follow-ups

### Pitfalls
- In Python `heapq`, `(node.val, node)` throws `TypeError` on tie-breaks because `ListNode` lacks `<`; break ties with unique index `i` `(node.val, i, node)` or merge bottom-up in O(1) space.

### Follow-ups
- External merge sort on disk streams chunks via a k-way min-heap buffer.