LinkedListProblem 31 of 36
Merge K sorted Linked list
Merge K Sorted Linked Lists
Problem Statement
Given k sorted linked lists, merge them into one sorted linked list. Each of the k lists is sorted in ascending order.
Example
Input:
lists = [
1 -> 4 -> 5,
1 -> 3 -> 4,
2 -> 6
]
Output: 1 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5 -> 6
Brute Force Approach (Merge One by One)
Intuition
Merge lists one by one. Start with the first list, merge it with the second, then merge the result with the third, and so on.
Algorithm
- Start with result = lists[0]
- For each subsequent list, merge it with result
- Use the standard merge two sorted lists technique
- Return the final merged result
Code
java
import java.util.List;
class Node {
int data;
Node next;
Node(int data) {
this.data = data;
this.next = null;
}
}
public class MergeKListsBrute {
public static Node mergeTwoLists(Node l1, Node l2) {
Node dummy = new Node(0);
Node tail = dummy;
while (l1 != null && l2 != null) {
if (l1.data <= l2.data) {
tail.next = l1;
l1 = l1.next;
} else {
tail.next = l2;
l2 = l2.next;
}
tail = tail.next;
}
tail.next = (l1 != null) ? l1 : l2;
return dummy.next;
}
public static Node mergeKListsBruteForce(List<Node> lists) {
if (lists == null || lists.isEmpty()) return null;
Node result = lists.get(0);
// Merge one by one
for (int i = 1; i < lists.size(); i++) {
result = mergeTwoLists(result, lists.get(i));
}
return result;
}
public static void printList(Node head) {
while (head != null) {
System.out.print(head.data);
if (head.next != null) System.out.print(" -> ");
head = head.next;
}
System.out.println();
}
}Complexity Analysis
- Time Complexity: O(k * N) where N is total number of nodes - Each merge can take O(N) and we do k-1 merges
- Space Complexity: O(1) - Only using constant extra space
Optimal Approach (Using Min-Heap)
Intuition
Use a min-heap to always get the smallest element among all current heads of the k lists. This avoids redundant comparisons and achieves O(log k) for finding minimum.
Algorithm
- Create a min-heap and insert the head of each non-empty list
- While heap is not empty:
- Extract the minimum node
- Add it to the result list
- If the extracted node has a next, insert next into heap
- Return the merged list
Code
java
import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
class Node {
int data;
Node next;
Node(int data) {
this.data = data;
this.next = null;
}
}
public class MergeKListsOptimal {
public static Node mergeKListsOptimal(List<Node> lists) {
PriorityQueue<Node> minHeap = new PriorityQueue<>((a, b) -> a.data - b.data);
// Insert head of each non-empty list
for (Node list : lists) {
if (list != null) {
minHeap.offer(list);
}
}
Node dummy = new Node(0);
Node tail = dummy;
while (!minHeap.isEmpty()) {
// Extract minimum
Node minNode = minHeap.poll();
// Add to result
tail.next = minNode;
tail = tail.next;
// If there's a next node, add it to heap
if (minNode.next != null) {
minHeap.offer(minNode.next);
}
}
return dummy.next;
}
public static void printList(Node head) {
while (head != null) {
System.out.print(head.data);
if (head.next != null) System.out.print(" -> ");
head = head.next;
}
System.out.println();
}
public static Node createList(int[] values) {
if (values.length == 0) return null;
Node head = new Node(values[0]);
Node curr = head;
for (int i = 1; i < values.length; i++) {
curr.next = new Node(values[i]);
curr = curr.next;
}
return head;
}
public static void main(String[] args) {
List<Node> lists = new ArrayList<>();
lists.add(createList(new int[]{1, 4, 5}));
lists.add(createList(new int[]{1, 3, 4}));
lists.add(createList(new int[]{2, 6}));
System.out.println("Input lists:");
for (int i = 0; i < lists.size(); i++) {
System.out.print("List " + (i + 1) + ": ");
printList(lists.get(i));
}
Node merged = mergeKListsOptimal(lists);
System.out.print("\nMerged list: ");
printList(merged);
}
}Complexity Analysis
- Time Complexity: O(N * log k) where N is total nodes - Each insertion/extraction from heap is O(log k)
- Space Complexity: O(k) - Heap stores at most k elements
Alternative: Divide and Conquer
Code (Divide and Conquer)
Complexity (Divide and Conquer)
- Time Complexity: O(N * log k) - log k levels, each processing all N nodes
- Space Complexity: O(log k) - Recursion stack
Comparison of Approaches
| Approach | Time | Space | Notes | |----------|------|-------|-------| | Merge One by One | O(kN) | O(1) | Simple but inefficient | | Min-Heap | O(Nlog k) | O(k) | Best for streaming data | | Divide and Conquer | O(N*log k) | O(log k) | Similar to merge sort |
Key Takeaways
- Min-Heap for K-way Merge: Classic technique for merging multiple sorted sequences
- Time Optimization: From O(kN) to O(Nlog k) using heap
- Divide and Conquer: Recursively merge pairs - similar complexity to heap
- Space Trade-off: Heap uses O(k), D&C uses O(log k) stack space
- Practical Usage: Used in external sorting, database merge operations
- Interview Classic: LeetCode #23 - Merge k Sorted Lists
- Generalization: Same pattern works for k-way merge of arrays, files, etc.