🧩 Problem Description
You are given an array of k linked lists, each sorted in ascending order.
Merge all the linked lists into one sorted linked list and return it.
💬 Example
1
2
| Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
|
💡 Approach 1: Min-Heap (Priority Queue)
Use a min-heap (priority queue) to always pull the smallest current node across all lists.
🔢 Java Code (PriorityQueue)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| class Solution {
public ListNode mergeKLists(ListNode[] lists) {
if (lists == null || lists.length == 0) return null;
PriorityQueue<ListNode> heap = new PriorityQueue<>(
(a, b) -> a.val - b.val
);
for (ListNode node : lists) {
if (node != null) heap.offer(node);
}
ListNode dummy = new ListNode(0);
ListNode curr = dummy;
while (!heap.isEmpty()) {
ListNode min = heap.poll();
curr.next = min;
curr = curr.next;
if (min.next != null) heap.offer(min.next);
}
return dummy.next;
}
}
|
⏱ Complexity (Heap Version)
- Time Complexity: O(N log k)
- N = total number of nodes
- k = number of lists
- Space Complexity: O(k) for the heap
💡 Approach 2: Divide and Conquer
Merge lists in pairs, just like how merge sort works.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
| class Solution {
public ListNode mergeKLists(ListNode[] lists) {
if (lists == null || lists.length == 0) return null;
return merge(lists, 0, lists.length - 1);
}
private ListNode merge(ListNode[] lists, int left, int right) {
if (left == right) return lists[left];
int mid = left + (right - left) / 2;
ListNode l1 = merge(lists, left, mid);
ListNode l2 = merge(lists, mid + 1, right);
return mergeTwoLists(l1, l2);
}
private ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(0), curr = dummy;
while (l1 != null && l2 != null) {
if (l1.val <= l2.val) {
curr.next = l1;
l1 = l1.next;
} else {
curr.next = l2;
l2 = l2.next;
}
curr = curr.next;
}
curr.next = (l1 != null) ? l1 : l2;
return dummy.next;
}
}
|
⏱ Complexity (Divide & Conquer)
- Time Complexity: O(N log k)
- Space Complexity: O(log k) due to recursion
✍️ Summary
- PriorityQueue approach is clean and uses a heap to track minimums.
- Divide & conquer approach is elegant and more space-efficient.
- Mastering this helps with:
lc-148 (Sort List)lc-21 (Merge 2 Sorted Lists)lc-218 (The Skyline Problem — heap merge concept)
Efficient merging is a key skill when working with linked lists and sorted data.