Merge k Sorted Lists
Problem
Given an array of k linked-lists lists, each linked-list is sorted in ascending order, merge all the linked-lists into one sorted linked-list and return it.
- k == lists.length
- 0 ≤ k ≤ 10⁴
- 0 ≤ lists[i].length ≤ 500
- −10⁴ ≤ lists[i][j] ≤ 10⁴
- lists[i] is sorted in ascending order.
- The sum of lists[i].length won't exceed 10⁴.
Example
lists = [[1,4,5],[1,3,4],[2,6]][1,1,2,3,4,4,5,6]The brute-force approach concatenates all lists and sorts them, which is inefficient. Instead, the algorithm uses a min-heap to efficiently track the smallest current node among all lists. Initially, the heap contains the first node of each list. The algorithm repeatedly extracts the smallest node from the heap, appends it to the merged list, and if the extracted node has a next node, it pushes that next node into the heap. This process continues until the heap is empty, resulting in a fully merged sorted list.
Approach
Straightforward Solution
A naive approach concatenates all nodes into one list and sorts it, resulting in O(N log N) time where N is the total number of nodes. This is inefficient for large inputs.
Core Observation
Merging k sorted lists requires repeatedly selecting the smallest current element among the heads of all lists. This is a classic problem of efficiently merging multiple sorted sequences.
Path to Optimal
The key insight is to use a min-heap (priority queue) to keep track of the smallest current node among the k lists. By pushing the first node of each list into the heap, the algorithm can extract the minimum node in O(log k) time and then push the next node from that list. This reduces the complexity to O(N log k), where N is the total number of nodes.
Optimal Approach
Use a min-heap to store the current nodes of each list. Initialize the heap with the first node of each non-empty list. Repeatedly pop the smallest node from the heap, append it to the merged list, and if the popped node has a next node, push it into the heap. Continue until the heap is empty. This approach efficiently merges all lists in O(N log k) time.
Time
O(N log k)
Each of the N nodes is pushed and popped from the heap at most once. Each heap operation takes O(log k) time because the heap size is at most k.
Space
O(k)
The heap stores at most one node from each of the k lists at any time, resulting in O(k) auxiliary space.
Pattern Spotlight
Heaps (Priority Queue for Merging Sorted Sequences)
When merging multiple sorted sequences, maintain a min-heap of the current smallest elements from each sequence to efficiently extract the global minimum and advance pointers, reducing the problem from O(N log N) to O(N log k).
Solution
| 1 | import heapq |
| 2 | |
| 3 | class Solution: |
| 4 | def mergeKLists(self, lists: list[ListNode]) -> ListNode: |
| 5 | heap = [] |
| 6 | |
| 7 | for source, head in enumerate(lists): |
| 8 | if head is not None: |
| 9 | heapq.heappush(heap, (head.val, source, head)) |
| 10 | |
| 11 | dummy = ListNode() |
| 12 | tail = dummy |
| 13 | |
| 14 | while heap: |
| 15 | _, source, node = heapq.heappop(heap) |
| 16 | next_node = node.next |
| 17 | |
| 18 | tail.next = node |
| 19 | tail = node |
| 20 | tail.next = None |
| 21 | |
| 22 | if next_node is not None: |
| 23 | heapq.heappush(heap, (next_node.val, source, next_node)) |
| 24 | |
| 25 | return dummy.next |
| 1 | import java.util.PriorityQueue; |
| 2 | |
| 3 | class Solution { |
| 4 | public ListNode mergeKLists(ListNode[] lists) { |
| 5 | PriorityQueue<ListNode> heap = new PriorityQueue<>((a, b) -> Integer.compare(a.val, b.val)); |
| 6 | |
| 7 | for (ListNode head : lists) { |
| 8 | if (head != null) { |
| 9 | heap.offer(head); |
| 10 | } |
| 11 | } |
| 12 | |
| 13 | ListNode dummy = new ListNode(0); |
| 14 | ListNode tail = dummy; |
| 15 | |
| 16 | while (!heap.isEmpty()) { |
| 17 | ListNode node = heap.poll(); |
| 18 | ListNode nextNode = node.next; |
| 19 | |
| 20 | tail.next = node; |
| 21 | tail = node; |
| 22 | tail.next = null; |
| 23 | |
| 24 | if (nextNode != null) { |
| 25 | heap.offer(nextNode); |
| 26 | } |
| 27 | } |
| 28 | |
| 29 | return dummy.next; |
| 30 | } |
| 31 | } |
| 1 | #include <queue> |
| 2 | #include <vector> |
| 3 | using namespace std; |
| 4 | |
| 5 | class Solution { |
| 6 | struct Compare { |
| 7 | bool operator()(ListNode* a, ListNode* b) const { |
| 8 | return a->val > b->val; |
| 9 | } |
| 10 | }; |
| 11 | |
| 12 | public: |
| 13 | ListNode* mergeKLists(vector<ListNode*>& lists) { |
| 14 | priority_queue<ListNode*, vector<ListNode*>, Compare> heap; |
| 15 | |
| 16 | for (ListNode* head : lists) { |
| 17 | if (head != nullptr) { |
| 18 | heap.push(head); |
| 19 | } |
| 20 | } |
| 21 | |
| 22 | ListNode dummy; |
| 23 | ListNode* tail = &dummy; |
| 24 | |
| 25 | while (!heap.empty()) { |
| 26 | ListNode* node = heap.top(); |
| 27 | heap.pop(); |
| 28 | |
| 29 | ListNode* nextNode = node->next; |
| 30 | tail->next = node; |
| 31 | tail = node; |
| 32 | tail->next = nullptr; |
| 33 | |
| 34 | if (nextNode != nullptr) { |
| 35 | heap.push(nextNode); |
| 36 | } |
| 37 | } |
| 38 | |
| 39 | return dummy.next; |
| 40 | } |
| 41 | }; |
| 1 | class MinHeap { |
| 2 | constructor() { |
| 3 | this.values = []; |
| 4 | } |
| 5 | |
| 6 | get size() { |
| 7 | return this.values.length; |
| 8 | } |
| 9 | |
| 10 | push(node) { |
| 11 | this.values.push(node); |
| 12 | let index = this.values.length - 1; |
| 13 | |
| 14 | while (index > 0) { |
| 15 | const parent = Math.floor((index - 1) / 2); |
| 16 | if (this.values[parent].val <= this.values[index].val) { |
| 17 | break; |
| 18 | } |
| 19 | |
| 20 | [this.values[parent], this.values[index]] = [this.values[index], this.values[parent]]; |
| 21 | index = parent; |
| 22 | } |
| 23 | } |
| 24 | |
| 25 | pop() { |
| 26 | if (this.values.length === 1) { |
| 27 | return this.values.pop(); |
| 28 | } |
| 29 | |
| 30 | const root = this.values[0]; |
| 31 | this.values[0] = this.values.pop(); |
| 32 | let index = 0; |
| 33 | |
| 34 | while (true) { |
| 35 | const left = index * 2 + 1; |
| 36 | const right = index * 2 + 2; |
| 37 | let smallest = index; |
| 38 | |
| 39 | if (left < this.values.length && this.values[left].val < this.values[smallest].val) { |
| 40 | smallest = left; |
| 41 | } |
| 42 | |
| 43 | if (right < this.values.length && this.values[right].val < this.values[smallest].val) { |
| 44 | smallest = right; |
| 45 | } |
| 46 | |
| 47 | if (smallest === index) { |
| 48 | break; |
| 49 | } |
| 50 | |
| 51 | [this.values[index], this.values[smallest]] = [this.values[smallest], this.values[index]]; |
| 52 | index = smallest; |
| 53 | } |
| 54 | |
| 55 | return root; |
| 56 | } |
| 57 | } |
| 58 | |
| 59 | var mergeKLists = function(lists) { |
| 60 | const heap = new MinHeap(); |
| 61 | |
| 62 | for (const head of lists) { |
| 63 | if (head !== null) { |
| 64 | heap.push(head); |
| 65 | } |
| 66 | } |
| 67 | |
| 68 | const dummy = new ListNode(0); |
| 69 | let tail = dummy; |
| 70 | |
| 71 | while (heap.size > 0) { |
| 72 | const node = heap.pop(); |
| 73 | const nextNode = node.next; |
| 74 | |
| 75 | tail.next = node; |
| 76 | tail = node; |
| 77 | tail.next = null; |
| 78 | |
| 79 | if (nextNode !== null) { |
| 80 | heap.push(nextNode); |
| 81 | } |
| 82 | } |
| 83 | |
| 84 | return dummy.next; |
| 85 | }; |
Step-by-Step Solution
Initialize Min-Heap with the First Node of Each List
| 1 | import heapq |
| 5 | heap = [] |
| 7 | for source, head in enumerate(lists): |
| 8 | if head is not None: |
| 9 | heapq.heappush(heap, (head.val, source, head)) |
| 11 | dummy = ListNode() |
| 12 | tail = dummy |
Objective
To prepare a min-heap containing the first node of each non-empty linked list for efficient minimum extraction.
Key Insight
By pushing the first node of each list into the heap, the algorithm sets up a data structure that always contains the smallest current candidates from all lists. This enables efficient retrieval of the next smallest node to append to the merged list. The heap stores tuples of (node value, source list index, node) to handle nodes with equal values and maintain stable ordering.
Interview Quick-Check
Core Logic
The heap stores tuples with node value and source index to ensure correct ordering and to distinguish nodes with identical values.
Common Pitfalls & Bugs
Forgetting to check if a list is empty before pushing its head into the heap can cause errors.
State & Boundaries
Only non-null heads are pushed into the heap to avoid invalid entries.
Build the Merged List by Extracting Minimum Nodes and Pushing Next Nodes
| 14 | while heap: |
| 15 | _, source, node = heapq.heappop(heap) |
| 16 | next_node = node.next |
| 18 | tail.next = node |
| 19 | tail = node |
| 20 | tail.next = None |
| 22 | if next_node is not None: |
| 23 | heapq.heappush(heap, (next_node.val, source, next_node)) |
Objective
To iteratively extract the smallest node from the heap, append it to the merged list, and push the next node from the same list into the heap if it exists.
Key Insight
The heap ensures that the smallest node among all current heads is always accessible in O(1) time (pop in O(log k)). After appending this node to the merged list, pushing its next node maintains the heap's invariant. This process continues until all nodes are merged, guaranteeing a sorted merged list. Setting tail.next to None after appending prevents accidental cycles.
Interview Quick-Check
Core Logic
Extracting the smallest node and pushing its successor maintains the heap invariant and ensures the merged list is sorted.
State & Boundaries
The loop continues until the heap is empty, meaning all nodes have been processed.
Common Pitfalls & Bugs
Forgetting to set tail.next to None can cause cycles or incorrect list termination.
Return the Head of the Fully Merged Sorted List
| 25 | return dummy.next |
Objective
To return the merged linked list starting from the node following the dummy head.
Key Insight
Using a dummy head simplifies list construction by avoiding special cases for the first node. Returning dummy.next gives the actual head of the merged list, which contains all nodes in sorted order.
Interview Quick-Check
Core Logic
Returning dummy.next skips the placeholder node and returns the true head of the merged list.
Line Analysis
This solution has 3 Critical lines interviewers watch for.
heapq.heappush(heap, (head.val, source, head))Push the tuple (node value, source index, node) into the heap.
Storing the node value as the first element ensures the heap orders nodes by their values. Including the source index breaks ties when values are equal, preventing comparison errors between ListNode objects.
_, source, node = heapq.heappop(heap)Pop the smallest node tuple from the heap.
Extracting the minimum node maintains the sorted order of the merged list by always selecting the next smallest element.
if next_node is not None:If the next node exists, push it into the heap.
Pushing the successor node maintains the heap invariant and ensures all nodes from each list are eventually merged.
heap = []Initialize an empty min-heap to store nodes.
The min-heap is the core data structure enabling efficient retrieval of the smallest node among all current list heads, which is essential for merging k sorted lists optimally.
tail.next = nodeAppend the extracted node to the merged list.
Linking the smallest node to the merged list builds the final sorted list incrementally.
tail.next = NoneSet tail.next to None to terminate the list.
Explicitly terminating the list prevents accidental cycles or dangling pointers, ensuring the merged list is well-formed.
heapq.heappush(heap, (next_node.val, source, next_node))Push the tuple (next node value, source index, next node) into the heap.
Including the source index and node value maintains heap ordering and tie-breaking, enabling correct and efficient merging.
import heapqImport the min-heap operations used by the solution.
heapq provides the push and pop operations needed to maintain the smallest current list head efficiently.
if head is not None:Check if the current list head is not None.
Only non-empty lists contribute nodes to the heap; this check prevents pushing invalid None entries that would cause errors.
dummy = ListNode()Create a dummy head for the merged list.
The dummy head removes the need to special-case the first node appended to the result.
tail = dummyInitialize tail at the dummy head.
Tail tracks the end of the merged list so each selected node can be appended in constant time.
next_node = node.nextStore the next node of the extracted node.
Tracking the next node allows the algorithm to continue merging nodes from the same source list by pushing successors into the heap.
tail = nodeAdvance the tail pointer to the newly appended node.
Updating the tail pointer maintains the end of the merged list for subsequent appends.
return dummy.nextReturn the head of the merged linked list.
Returning dummy.next skips the placeholder node and provides the caller with the fully merged sorted list.
while heap:Continue looping while the heap is not empty.
The loop processes all nodes by repeatedly extracting the smallest node until no nodes remain, ensuring complete merging.
for source, head in enumerate(lists):Iterate over each list with its index.
Enumerating lists with their indices allows tracking the source list of each node, which is necessary to push the next node from the correct list into the heap.
Test Your Understanding
Why does using a min-heap reduce the time complexity from O(N log N) to O(N log k)?
Because the heap size is limited to k (the number of lists), each insertion and extraction takes O(log k) time instead of O(log N), and since each of the N nodes is processed once, the total time is O(N log k).
Related Problems
Heaps pattern
Don't just read it. Drill it.
Reconstruct Merge k Sorted Lists from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Merge k Sorted Lists drill