Merge K Sorted Lists

Hardlinked-listheapdivide-and-conquer
Category: Linked List
Companies that ask this question:
AmazonFacebookGoogleMicrosoftUber
LeetCode →NeetCode →

Approach

Merge K Sorted Lists

Problem Statement

You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.

Merge all the linked-lists into one sorted linked-list and return it.

Approach: Min-Heap (Priority Queue)

The optimal solution uses a min-heap to efficiently merge all k sorted lists.

Algorithm

  1. Initialize Min-Heap: Create a min-heap and insert the first node from each non-empty list
  2. Merge Process:
    • Extract the minimum node from the heap
    • Add it to the result list
    • If the extracted node has a next node, insert it into the heap
  3. Repeat: Continue until the heap is empty

Why Min-Heap?

  • At each step, we need to find the minimum among the current heads of all k lists
  • A min-heap allows us to find the minimum in O(log k) time
  • Without a heap, comparing k elements each time would take O(k) time

Time Complexity

  • Time: O(N log k), where N is the total number of nodes across all lists
    • Each node is inserted and extracted from the heap once: O(log k) per operation
    • Total operations: N insertions + N extractions = 2N operations
  • Space: O(k) for the heap, storing at most k nodes at a time

Example Walkthrough

For lists: [[1,4,5], [1,3,4], [2,6]]

  1. Initial Heap: [1(L0), 1(L1), 2(L2)]
  2. Step 1: Extract 1(L0), add 4(L0) to heap → Result: [1]
  3. Step 2: Extract 1(L1), add 3(L1) to heap → Result: [1,1]
  4. Step 3: Extract 2(L2), add 6(L2) to heap → Result: [1,1,2]
  5. Continue: Until all nodes are processed

Alternative Approaches

1. Divide and Conquer (Merge Pairs)

  • Merge lists in pairs: k lists → k/2 lists → k/4 lists → ... → 1 list
  • Time: O(N log k), Space: O(1) if we modify lists in-place
  • Similar time complexity but requires more complex implementation

2. Sequential Merging

  • Merge list 1 with list 2, then merge result with list 3, etc.
  • Time: O(kN), Space: O(1)
  • Simple but inefficient for large k

Key Insights

  1. The min-heap approach is optimal for this problem
  2. We only need to keep track of one node from each list at a time
  3. The heap size never exceeds k, making it space-efficient
  4. This pattern applies to merging any k sorted sequences

Solution

java
1/**
2 * Merge K Sorted Lists - Min-Heap Approach
3 *
4 * Time Complexity: O(N log k) where N is total nodes, k is number of lists
5 * Space Complexity: O(k) for the heap
6 */
7
8import java.util.*;
9
10class ListNode {
11    int val;
12    ListNode next;
13    ListNode() {}
14    ListNode(int val) { this.val = val; }
15    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
16}
17
18class Solution {
19    public ListNode mergeKLists(ListNode[] lists) {
20        // Edge case: empty lists
21        if (lists == null || lists.length == 0) {
22            return null;
23        }
24
25        // Initialize min-heap with custom comparator
26        PriorityQueue<ListNode> minHeap = new PriorityQueue<>(
27            (a, b) -> a.val - b.val
28        );
29
30        // Add first node from each non-empty list
31        for (ListNode head : lists) {
32            if (head != null) {
33                minHeap.offer(head);
34            }
35        }
36
37        // Create dummy node for result
38        ListNode dummy = new ListNode(0);
39        ListNode current = dummy;
40
41        // Process heap until empty
42        while (!minHeap.isEmpty()) {
43            // Extract minimum node
44            ListNode minNode = minHeap.poll();
45
46            // Add to result list
47            current.next = minNode;
48            current = current.next;
49
50            // If extracted node has a next, add it to heap
51            if (minNode.next != null) {
52                minHeap.offer(minNode.next);
53            }
54        }
55
56        return dummy.next;
57    }
58}
59
60// Alternative: Divide and Conquer
61class Solution2 {
62    public ListNode mergeKLists(ListNode[] lists) {
63        if (lists == null || lists.length == 0) {
64            return null;
65        }
66
67        List<ListNode> listList = new ArrayList<>(Arrays.asList(lists));
68
69        // Merge lists in pairs until only one remains
70        while (listList.size() > 1) {
71            List<ListNode> mergedLists = new ArrayList<>();
72
73            // Merge pairs
74            for (int i = 0; i < listList.size(); i += 2) {
75                ListNode l1 = listList.get(i);
76                ListNode l2 = i + 1 < listList.size() ? listList.get(i + 1) : null;
77                mergedLists.add(mergeTwoLists(l1, l2));
78            }
79
80            listList = mergedLists;
81        }
82
83        return listList.get(0);
84    }
85
86    private ListNode mergeTwoLists(ListNode l1, ListNode l2) {
87        ListNode dummy = new ListNode(0);
88        ListNode current = dummy;
89
90        while (l1 != null && l2 != null) {
91            if (l1.val < l2.val) {
92                current.next = l1;
93                l1 = l1.next;
94            } else {
95                current.next = l2;
96                l2 = l2.next;
97            }
98            current = current.next;
99        }
100
101        current.next = l1 != null ? l1 : l2;
102        return dummy.next;
103    }
104}
105
Loading visualizer...