-
Notifications
You must be signed in to change notification settings - Fork 0
074 — Merge k Sorted Lists
LeetCode 23 · Hard. You are given an array of k linked-list heads, each sorted in ascending order. Merge all the lists into one sorted linked list and return its head.
This is Merge Two Sorted Lists, but instead of two lines of people you now have k of them, all pre-sorted, and you need to repeatedly pull the smallest front-of-line person across all the lines. With only two lines, one comparison per step is enough. With k lines, comparing all k front values every single step is wasteful once k grows — what you actually need is a structure that hands you "the current smallest among many candidates" instantly, and updates itself cheaply whenever that smallest one gets replaced. That's precisely what a heap is built for.
"k sorted lists" or "k sorted arrays", plus "merge", is the direct trigger for the top-K/heap pattern. Any time you need "the smallest (or largest) among a changing set of candidates, repeatedly," a min-heap of the current candidates turns each "find the smallest of k" step from O(k) (scanning all of them) into O(log k) (peeking the heap's root and re-heapifying).
Dump every value from every list into one array, sort it, then rebuild a single list — ignoring that each individual list was already sorted.
class ListNode {
var val: Int
var next: ListNode?
init(_ val: Int) { self.val = val }
}
func mergeKListsBruteForce(_ lists: [ListNode?]) -> ListNode? {
var values: [Int] = []
for list in lists {
var curr = list
while let node = curr {
values.append(node.val)
curr = node.next
}
}
values.sort()
let dummy = ListNode(0)
var tail = dummy
for v in values {
tail.next = ListNode(v)
tail = tail.next!
}
return dummy.next
}
// smoke test: [1,4,5], [1,3,4], [2,6]
func buildList(_ values: [Int]) -> ListNode? {
let dummy = ListNode(0)
var tail = dummy
for v in values { tail.next = ListNode(v); tail = tail.next! }
return dummy.next
}
let bfLists: [ListNode?] = [buildList([1, 4, 5]), buildList([1, 3, 4]), buildList([2, 6])]
var bfWalk: ListNode? = mergeKListsBruteForce(bfLists)
while let n = bfWalk { print(n.val, terminator: " "); bfWalk = n.next } // 1 1 2 3 4 4 5 6Big-O: Let N be the total number of nodes across all lists. O(N log N) time, dominated by the sort, discarding the fact each individual list arrived pre-sorted. O(N) extra space for the values array.
Keep a min-heap of "the current head of each list still in play." Repeatedly pop the smallest, append it to the result, and push whatever node came after it in its original list.
func mergeKLists(_ lists: [ListNode?]) -> ListNode? {
// Minimal array-backed min-heap of list nodes, ordered by node.val.
var heap: [ListNode] = lists.compactMap { $0 }
func siftDown(_ index: Int) {
var parent = index
while true {
let left = 2 * parent + 1
let right = 2 * parent + 2
var smallest = parent
if left < heap.count && heap[left].val < heap[smallest].val { smallest = left }
if right < heap.count && heap[right].val < heap[smallest].val { smallest = right }
if smallest == parent { return }
heap.swapAt(parent, smallest)
parent = smallest
}
}
func siftUp(_ index: Int) {
var child = index
var parent = (child - 1) / 2
while child > 0 && heap[child].val < heap[parent].val {
heap.swapAt(child, parent)
child = parent
parent = (child - 1) / 2
}
}
// Heapify all k initial heads in O(k).
if heap.count > 1 {
for i in stride(from: heap.count / 2 - 1, through: 0, by: -1) {
siftDown(i)
}
}
let dummy = ListNode(0)
var tail = dummy
while !heap.isEmpty {
let smallest = heap[0]
tail.next = smallest
tail = tail.next!
heap[0] = heap[heap.count - 1]
heap.removeLast()
if !heap.isEmpty {
siftDown(0)
}
if let next = smallest.next {
heap.append(next)
siftUp(heap.count - 1)
}
}
return dummy.next
}
// smoke test: [1,4,5], [1,3,4], [2,6]
let lists: [ListNode?] = [buildList([1, 4, 5]), buildList([1, 3, 4]), buildList([2, 6])]
var walk: ListNode? = mergeKLists(lists)
while let n = walk { print(n.val, terminator: " "); walk = n.next } // 1 1 2 3 4 4 5 6
// smoke test: empty input
print(mergeKLists([]) == nil) // true
print(mergeKLists([nil, nil]) == nil) // trueBig-O: O(N log k) time, where N is the total number of nodes and k is the number of lists — each of the N nodes is pushed and popped from a heap of size at most k, each operation costing O(log k). O(k) extra space for the heap.
With only two lists, "find the smaller of the two current fronts" is a single comparison — cheap enough to just do directly. With k lists, that same idea scaled up naively means comparing all k current fronts on every single step, which is O(k) per node and O(Nk) overall — worse than just sorting everything. A heap fixes this by never re-scanning: it keeps the k current candidates in a structure where the minimum is always at the root in O(1) to read, and swapping it out (pop the min, push its list's next node) costs only O(log k) to restore the heap property — not O(k). That's the same trade-off the Top-K and Heap Pattern chapter describes: avoid paying for a full sort when you only ever need repeated access to "the current extreme."
- Linked Lists — the underlying per-list data structure; nodes are spliced into the result list directly, never copied.
-
Heaps & Priority Queues — the data structure behind the optimal approach; the heap here holds
ListNodereferences ordered byval, sifting up/down exactly as described in that chapter. -
Top-K and Heap Pattern — the pattern this problem is a genuine, standard instance of: a min-heap of
kcandidates, repeatedly extracting the current smallest. -
Merge Two Sorted Lists — the
k = 2special case, where a single comparison replaces the need for a heap entirely.
Merge k Sorted Lists is Merge Two Sorted Lists scaled up — instead of comparing two front-runners by hand, a min-heap always hands you the current fastest one instantly.
In the optimal solution, every time a node is popped from the heap, its list's next node (if any) is immediately pushed back in. Explain why this is enough to guarantee that no node is ever emitted out of order — that is, why can't a smaller value "hiding" further down one of the lists ever sneak past the heap and get skipped?