You are given an array of k linked lists lists,
each sorted in ascending order. Merge all the linked lists into one sorted linked list and return it.
Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
Input: lists = []
Output: []
Constraints:
- k == lists.length
- 0 <= k <= 104
- Each list is sorted in ascending order. Total nodes across all lists ≤ 104.
Contents
- Approach 1 — Brute Force (collect and sort)
- Approach 2 — Min-Heap (Optimal)
- Complexity Analysis
Brute Force
Collect all values into a list, sort it, rebuild the linked list.
public ListNode mergeKLists(ListNode[] lists) {
List<Integer> values = new ArrayList<>();
for (ListNode list : lists) {
while (list != null) {
values.add(list.val);
list = list.next;
}
}
Collections.sort(values);
ListNode dummy = new ListNode(0);
ListNode curr = dummy;
for (int v : values) {
curr.next = new ListNode(v);
curr = curr.next;
}
return dummy.next;
}
// Time: O(N log N) where N = total nodes. Space: O(N)
Min-Heap
Always extract the globally minimum node from the k current list heads.
Use a min-heap to efficiently find the minimum among the heads.
Algorithm:
- Push the head node of each list into the min-heap (ordered by val).
- Pop the minimum node, append it to the result, then push its next node (if any) into the heap.
- Repeat until the heap is empty.
public ListNode mergeKLists(ListNode[] lists) {
// Min-heap ordered by node value
PriorityQueue<ListNode> minHeap = new PriorityQueue<>(
Comparator.comparingInt(n -> n.val)
);
// Initialise heap with the head of each non-null list
for (ListNode list : lists) {
if (list != null) minHeap.offer(list);
}
ListNode dummy = new ListNode(0);
ListNode curr = dummy;
while (!minHeap.isEmpty()) {
ListNode node = minHeap.poll(); // smallest current head
curr.next = node;
curr = curr.next;
if (node.next != null) {
minHeap.offer(node.next); // push the next node from the same list
}
}
return dummy.next;
}
| Approach | Time | Space |
|---|
| Brute Force | O(N log N) | O(N) |
| Min-Heap | O(N log k) | O(k) — heap holds at most k nodes |
N = total number of nodes across all lists, k = number of lists.