Losing head/tail while rewiring
Wrong move: Pointer updates overwrite references before they are saved.
Usually fails on: List becomes disconnected mid-operation.
Fix: Store next pointers first and use a dummy head for safer joins.
A complete visual walkthrough of the min-heap approach — from brute force to the optimal O(N log k) solution.
You are 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.
Example 1:
Input: lists = [[1,4,5],[1,3,4],[2,6]] Output: [1,1,2,3,4,4,5,6] Explanation: The linked-lists are: [ 1->4->5, 1->3->4, 2->6 ] merging them into one sorted linked list: 1->1->2->3->4->4->5->6
Example 2:
Input: lists = [] Output: []
Example 3:
Input: lists = [[]] Output: []
Constraints:
k == lists.length0 <= k <= 1040 <= lists[i].length <= 500-104 <= lists[i][j] <= 104lists[i] is sorted in ascending order.lists[i].length will not exceed 104.Before optimizing, let's see two straightforward approaches and understand why they fall short.
Gather all values from every list into an array, sort the array, then build a new linked list from the sorted values.
Time: O(N log N) where N = total number of nodes across all lists. Space: O(N) for the array. This ignores the sorted structure entirely.
Merge list 1 with list 2, then merge the result with list 3, and so on. Each merge is O(n), but the accumulated list keeps growing.
Total work: 2n + 3n + ... + kn = O(kN). If k is large, this is slow. We need something that considers all k lists simultaneously without redundant re-scanning.
The problem with both approaches: they don't exploit the fact that each list is already sorted. We want an approach that always picks the global minimum efficiently from the k list heads.
At any moment, the next node in the merged result must be the smallest head among all k lists. A min-heap lets us find that minimum in O(log k) time instead of O(k).
Think of k conveyor belts feeding into a single funnel (the heap). The heap always holds the front item from each belt and lets the smallest one through.
Why O(log k) per node? The heap never has more than k elements (one from each list). Every push/pop on a heap of size k costs O(log k). We do this N times total, giving O(N log k) overall.
Let's trace through the example: lists = [[1,4,5], [1,3,4], [2,6]]. We track the heap state and result at each step.
Push the head of each list into the heap.
Instead of a heap, we can pair up lists and merge them recursively, like merge sort. Each round halves the number of lists.
Each round does O(N) total work (every node is compared once). There are O(log k) rounds, giving the same O(N log k) overall time.
| Approach | Time | Space | Notes |
|---|---|---|---|
| Collect + Sort | O(N log N) | O(N) | Ignores sorted structure |
| Merge one by one | O(kN) | O(1) | Redundant re-scanning |
| Min-Heap | O(N log k) | O(k) | Optimal, straightforward |
| Divide & Conquer | O(N log k) | O(log k) | Optimal, recursive |
When to use which? The heap approach is simpler to implement and works well in interviews. Divide and conquer uses slightly less space (O(log k) stack vs. O(k) heap) and can be faster in practice due to cache locality during pairwise merges.
When lists is an empty array, the loop that seeds the heap pushes nothing, so the heap starts empty. The while (!pq.isEmpty()) loop never executes, and dummy.next remains null. The function returns null immediately — correct by definition since there are no nodes to merge.
The seeding loop explicitly guards with if (head != null), so any null entries in lists are silently skipped and never pushed onto the heap. Only nodes from valid, non-empty lists enter the priority queue. The result is identical to running the merge on the non-null sublists alone — no special handling is required downstream.
With exactly one non-null list, every node from that list is pushed onto the heap one at a time (head first, then each successive node as the previous one is popped). The heap never holds more than one element simultaneously, so no real comparison or reordering happens. The output linked list is a reconstruction of the single input list in the same order — effectively a pass-through at O(n log 1) = O(n) cost.
All k single-node lists are pushed into the heap during initialization, giving a heap of size k. Each poll() extracts the global minimum; since node.next == null for every node, nothing is re-inserted. The heap drains in exactly k pops, producing a sorted list of k elements. This is the case where the heap reaches its maximum initial size and every comparison is useful.
The algorithm handles skewed lengths naturally. A list with 10,000 nodes keeps feeding the heap one node at a time as its predecessors are popped, while shorter lists drain early and stop contributing. The heap size never exceeds k (one representative per list), regardless of how unequal the lengths are. Total work is O(N log k) where N is the total node count — there is no penalty for imbalance.
The priority queue (min-heap) approach in Java. Clean, concise, and handles all edge cases.
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public ListNode mergeKLists(ListNode[] lists) { // Min-heap ordered by node value PriorityQueue<ListNode> heap = new PriorityQueue<>((a, b) -> a.val - b.val); // Seed the heap with the head of every non-empty list for (ListNode node : lists) { if (node != null) heap.offer(node); } // Dummy head simplifies list-building logic ListNode dummy = new ListNode(0); ListNode curr = dummy; while (!heap.isEmpty()) { // Extract the global minimum ListNode min = heap.poll(); // Append to result list curr.next = min; curr = curr.next; // If this list has more nodes, push the next one if (min.next != null) { heap.offer(min.next); } } // Return the real head (skip dummy) return dummy.next; } }
import "container/heap" // nodeHeap implements heap.Interface for *ListNode type nodeHeap []*ListNode func (h nodeHeap) Len() int { return len(h) } func (h nodeHeap) Less(i, j int) bool { return h[i].Val < h[j].Val } func (h nodeHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] } func (h *nodeHeap) Push(x interface{}) { *h = append(*h, x.(*ListNode)) } func (h *nodeHeap) Pop() interface{} { old := *h; n := len(old); x := old[n-1]; *h = old[:n-1]; return x } func mergeKLists(lists []*ListNode) *ListNode { h := &nodeHeap{} // Seed the heap with the head of every non-empty list for _, node := range lists { if node != nil { heap.Push(h, node) } } heap.Init(h) // Dummy head simplifies list-building logic dummy := &ListNode{} curr := dummy for h.Len() > 0 { // Extract the global minimum min := heap.Pop(h).(*ListNode) // Append to result list curr.Next = min curr = curr.Next // If this list has more nodes, push the next one if min.Next != nil { heap.Push(h, min.Next) } } // Return the real head (skip dummy) return dummy.Next }
import heapq # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def merge_k_lists( self, lists: list[Optional[ListNode]] ) -> Optional[ListNode]: # Min-heap of (val, tie-breaker, node) heap: list[tuple[int, int, ListNode]] = [] idx = 0 # Seed the heap with the head of every non-empty list for node in lists: if node: heapq.heappush(heap, (node.val, idx, node)) idx += 1 # Dummy head simplifies list-building logic dummy = ListNode(0) curr = dummy while heap: # Extract the global minimum val, _, min_node = heapq.heappop(heap) # Append to result list curr.next = min_node curr = curr.next # If this list has more nodes, push the next one if min_node.next: heapq.heappush(heap, (min_node.next.val, idx, min_node.next)) idx += 1 # Return the real head (skip dummy) return dummy.next
use std::collections::BinaryHeap; use std::cmp::Reverse; impl Solution { pub fn merge_k_lists(lists: Vec<Option<Box<ListNode>>>) -> Option<Box<ListNode>> { // Min-heap: Reverse wraps (val, node) so BinaryHeap becomes a min-heap let mut heap: BinaryHeap<Reverse<(i32, Box<ListNode>)>> = BinaryHeap::new(); // Seed the heap with the head of every non-empty list for node in lists { if let Some(n) = node { heap.push(Reverse((n.val, n))); } } // Dummy head simplifies list-building logic let mut dummy = Box::new(ListNode::new(0)); let mut curr = &mut *dummy; while let Some(Reverse((_, mut node))) = heap.pop() { // If this list has more nodes, push the next one if let Some(next) = node.next.take() { heap.push(Reverse((next.val, next))); } // Append to result list curr.next = Some(node); curr = curr.next.as_mut().unwrap(); } // Return the real head (skip dummy) dummy.next } }
// Uses a MinPriorityQueue from @datastructures-js/priority-queue // (available on LeetCode's TypeScript environment) function mergeKLists(lists: (ListNode | null)[]): ListNode | null { // Min-heap ordered by node value const heap = new MinPriorityQueue<ListNode>({ compare: (a, b) => a.val - b.val, }); // Seed the heap with the head of every non-empty list for (const node of lists) { if (node !== null) heap.enqueue(node); } // Dummy head simplifies list-building logic const dummy = new ListNode(0); let curr = dummy; while (!heap.isEmpty()) { // Extract the global minimum const min = heap.dequeue(); // Append to result list curr.next = min; curr = curr.next; // If this list has more nodes, push the next one if (min.next !== null) { heap.enqueue(min.next); } } // Return the real head (skip dummy) return dummy.next; }
Comparator note: (a, b) -> a.val - b.val orders by ascending value. This is safe here because LeetCode constrains values to [-10^4, 10^4], so integer overflow won't occur. For arbitrary integers, use Integer.compare(a.val, b.val) instead.
class Solution { public ListNode mergeKLists(ListNode[] lists) { if (lists == null || lists.length == 0) return null; return divide(lists, 0, lists.length - 1); } private ListNode divide(ListNode[] lists, int lo, int hi) { if (lo == hi) return lists[lo]; int mid = (lo + hi) / 2; ListNode left = divide(lists, lo, mid); ListNode right = divide(lists, mid + 1, hi); return merge(left, right); } // Standard merge of two sorted lists private ListNode merge(ListNode a, ListNode b) { ListNode dummy = new ListNode(0), tail = dummy; while (a != null && b != null) { if (a.val <= b.val) { tail.next = a; a = a.next; } else { tail.next = b; b = b.next; } tail = tail.next; } tail.next = (a != null) ? a : b; return dummy.next; } }
func mergeKLists(lists []*ListNode) *ListNode { if len(lists) == 0 { return nil } return divide(lists, 0, len(lists)-1) } func divide(lists []*ListNode, lo, hi int) *ListNode { if lo == hi { return lists[lo] } mid := (lo + hi) / 2 left := divide(lists, lo, mid) right := divide(lists, mid+1, hi) return mergeTwoLists(left, right) } // Standard merge of two sorted lists func mergeTwoLists(a, b *ListNode) *ListNode { dummy := &ListNode{} tail := dummy for a != nil && b != nil { if a.Val <= b.Val { tail.Next = a; a = a.Next } else { tail.Next = b; b = b.Next } tail = tail.Next } if a != nil { tail.Next = a } else { tail.Next = b } return dummy.Next }
class Solution: def merge_k_lists( self, lists: list[Optional[ListNode]] ) -> Optional[ListNode]: if not lists: return None return self._divide(lists, 0, len(lists) - 1) def _divide( self, lists: list[Optional[ListNode]], lo: int, hi: int ) -> Optional[ListNode]: if lo == hi: return lists[lo] mid = (lo + hi) // 2 left = self._divide(lists, lo, mid) right = self._divide(lists, mid + 1, hi) return self._merge(left, right) # Standard merge of two sorted lists def _merge( self, a: Optional[ListNode], b: Optional[ListNode] ) -> Optional[ListNode]: dummy = ListNode(0) tail = dummy 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 if a else b return dummy.next
impl Solution { pub fn merge_k_lists(lists: Vec<Option<Box<ListNode>>>) -> Option<Box<ListNode>> { if lists.is_empty() { return None; } Self::divide(lists, 0) } fn divide(mut lists: Vec<Option<Box<ListNode>>>, _: usize) -> Option<Box<ListNode>> { while lists.len() > 1 { let mut next_round = Vec::new(); let mut i = 0; while i < lists.len() { if i + 1 < lists.len() { let merged = Self::merge_two(lists[i].take(), lists[i+1].take()); next_round.push(merged); i += 2; } else { next_round.push(lists[i].take()); i += 1; } } lists = next_round; } lists.into_iter().next().flatten() } // Standard merge of two sorted lists fn merge_two( a: Option<Box<ListNode>>, b: Option<Box<ListNode>>, ) -> Option<Box<ListNode>> { match (a, b) { (None, b) => b, (a, None) => a, (Some(mut a), Some(mut b)) => { if a.val <= b.val { a.next = Self::merge_two(a.next.take(), Some(b)); Some(a) } else { b.next = Self::merge_two(Some(a), b.next.take()); Some(b) } } } } }
function mergeKLists(lists: (ListNode | null)[]): ListNode | null { if (!lists || lists.length === 0) return null; return divide(lists, 0, lists.length - 1); } function divide( lists: (ListNode | null)[], lo: number, hi: number ): ListNode | null { if (lo === hi) return lists[lo]; const mid = (lo + hi) >> 1; const left = divide(lists, lo, mid); const right = divide(lists, mid + 1, hi); return merge(left, right); } // Standard merge of two sorted lists function merge( a: ListNode | null, b: ListNode | null ): ListNode | null { const dummy = new ListNode(0); let tail = dummy; while (a !== null && b !== null) { 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; }
Enter multiple sorted lists and watch the min-heap merge them step by step. See the heap contents, the extracted minimum, and the result building in real time.
Every node is pushed into and popped from the min-heap exactly once. The heap never holds more than k entries (one per list), so each insertion and extraction costs O(log k). With N total nodes across all lists, the total work is O(N log k). The heap itself uses O(k) space.
Merges lists one by one sequentially. Each merge scans up to N nodes, and we perform k-1 merges. The intermediate merged list grows each round, so total comparisons approach N·k. Only pointer variables are used.
Recursively splits the k lists in half, merges pairs bottom-up. There are log k levels of merging, and each level processes all N nodes exactly once. The recursion stack uses O(log k) frames.
Each of the N nodes is pushed into and popped from a heap of size k exactly once. Each heap operation costs O(log k), giving O(N log k) total. The heap holds one node per list, using O(k) memory.
The heap always holds exactly k elements -- one per list -- so each extraction is O(log k). Brute force merges lists one by one, scanning up to N nodes k times. Both the heap and divide-and-conquer approaches achieve O(N log k) by reducing the k-way decision to a logarithmic operation at each step.
Review these before coding to avoid predictable interview regressions.
Wrong move: Pointer updates overwrite references before they are saved.
Usually fails on: List becomes disconnected mid-operation.
Fix: Store next pointers first and use a dummy head for safer joins.