Problem Statement
Given K sorted linked lists, merge them into one sorted linked list.
Brute Force Intuition
Put all nodes into an array.
Sort the array.
Create a new linked list.
Complexity
- Time Complexity: O(N log N)
- Space Complexity: O(N)
Where:
N = Total Nodes
Better Heap Approach
Push first node of every list into Min Heap.
Repeatedly:
Take smallest node
Insert next node
Complexity
O(N log K)
Moving Towards Optimal
Instead of merging one list at a time:
Merge Lists Pairwise
Exactly like Merge Sort.
Pattern Recognition
Merge K Things
=> Divide and Conquer
Optimal Approach
K Lists
Split Into Two Halves
Merge Left
Merge Right
Merge Results
Optimal Java Solution
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
if (lists.length == 0)
return null;
return mergeKLists(
lists,
0,
lists.length - 1
);
}
private ListNode mergeKLists(
ListNode[] lists,
int si,
int ei) {
if (si == ei)
return lists[si];
int mid = (si + ei) / 2;
ListNode left =
mergeKLists(lists, si, mid);
ListNode right =
mergeKLists(lists, mid + 1, ei);
return mergeTwoLists(left, right);
}
private ListNode mergeTwoLists(
ListNode l1,
ListNode l2) {
ListNode dummy =
new ListNode(-1);
ListNode 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;
}
}
Dry Run
1→4→5
1→3→4
2→6
Merge:
(1→4→5) + (1→3→4)
=
1→1→3→4→4→5
Merge with:
2→6
Final:
1→1→2→3→4→4→5→6
Complexity Analysis
| Metric | Complexity |
|---|---|
| Time | O(N log K) |
| Space | O(log K) |
Interview One-Liner
Use Divide & Conquer like Merge Sort by recursively merging pairs of linked lists.