Merge k Sorted Lists
Problem
k singly linked lists, each already sorted in
ascending order (some may be empty, and the array itself may be empty). Combine them into
one ascending linked list and return its head.[[1,4,5],[1,3,4],[2,6]]Output[1,1,2,3,4,4,5,6][]Output[][[]]Output[]0 ≤ k ≤ 104 · 0 ≤ list length ≤ 500 · -104 ≤ val ≤ 104 · total nodes N ≤ 104
Try it yourself
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
}
}
Instinct Several sorted lists, rows or streams and you need the global order, the k-th smallest or a range: keep one cursor per list in a min-heap.
Memory hack Line up the heads, crown the smallest, then let its next-in-line step up.
Open the K-Way Merge guide →Approaches
Brute ForceCollect All Values & Sort
O(N log N)Space O(N)Throw away the sortedness: dump every value into a list, sort it, and build a fresh linked list from the sorted values.
public ListNode mergeKLists(ListNode[] lists) { List<Integer> values = new ArrayList<>(); for (ListNode node : lists) { for (; node != null; node = node.next) values.add(node.val); } Collections.sort(values); ListNode dummy = new ListNode(0), tail = dummy; for (int v : values) { tail.next = new ListNode(v); tail = tail.next; } return dummy.next; }
Simple, but ignores that inputs are sorted and allocates N new nodes.
BetterMin-Heap of List Heads
O(N log k)Space O(k)Keep the current head of every non-empty list in a min-heap. Poll the smallest,
append it to the result, and push its next. The heap never holds more
than k nodes, so each of the N steps costs O(log k).
public ListNode mergeKLists(ListNode[] lists) { PriorityQueue<ListNode> heap = new PriorityQueue<>(Comparator.comparingInt(n -> n.val)); for (ListNode head : lists) { if (head != null) heap.offer(head); } ListNode dummy = new ListNode(0), tail = dummy; while (!heap.isEmpty()) { ListNode node = heap.poll(); tail.next = node; tail = node; if (node.next != null) heap.offer(node.next); } return dummy.next; }
Optimal time and reuses nodes; needs an O(k) heap.
OptimalDivide & Conquer Pairwise Merge
O(N log k)Space O(log k)Split the array of lists in half, merge each half recursively, then merge the two results with the classic two-list merge. The recursion has log k levels and every level touches each of the N nodes once (like merge sort).
public ListNode mergeKLists(ListNode[] lists) { if (lists.length == 0) return null; return merge(lists, 0, lists.length - 1); } private ListNode merge(ListNode[] lists, int lo, int hi) { if (lo == hi) return lists[lo]; int mid = lo + (hi - lo) / 2; return mergeTwo(merge(lists, lo, mid), merge(lists, mid + 1, hi)); } private ListNode mergeTwo(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; // attach the leftover tail return dummy.next; }
Same O(N log k) time, no heap, only the recursion stack — nodes relinked in place.
At a glance
| Level | Approach | Time | Space |
|---|---|---|---|
| Brute Force | Collect All Values & Sort | O(N log N) | O(N) |
| Better | Min-Heap of List Heads | O(N log k) | O(k) |
| Optimal | Divide & Conquer Pairwise Merge | O(N log k) | O(log k) |
- Pushing
nullheads into the heap — NPE in the comparator. - Merging sequentially (result = merge(result, listi)) — O(N·k), not O(N log k).
- Forgetting the empty-array case
k = 0in divide & conquer.
- State N (total nodes) vs k (lists) clearly before giving complexities.
- Offer both O(N log k) solutions and compare: heap = O(k) space, D&C = O(log k).
- Reuse Merge Two Sorted Lists (21) as a helper — say so explicitly.