HeapProblem 10 of 18Important

Merge K Sorted Linked Lists [V.IMP]

Brute Force
Time: O(N*K log(N*K))
Space: O(N*K)
Optimal
Time: O(N*K log K)
Space: O(K)

Problem Statement

Given K sorted linked lists, merge them into a single sorted linked list.

Example:

  • Input: lists = [ 1 -> 4 -> 5, 1 -> 3 -> 4, 2 -> 6 ]
  • Output: 1 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5 -> 6
  • Explanation: All three sorted lists are merged into one sorted list.

Approach 1: Collect All Nodes and Sort (Brute Force)

Intuition

Collect all node values, sort them, and create a new linked list.

Algorithm

  1. Traverse all linked lists and collect values
  2. Sort the collected values
  3. Create a new linked list from sorted values
java
import java.util.*;

class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }
}

public class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        List<Integer> values = new ArrayList<>();
        
        // Collect all values
        for (ListNode list : lists) {
            while (list != null) {
                values.add(list.val);
                list = list.next;
            }
        }
        
        // Sort values
        Collections.sort(values);
        
        // Create new linked list
        ListNode dummy = new ListNode(0);
        ListNode curr = dummy;
        
        for (int val : values) {
            curr.next = new ListNode(val);
            curr = curr.next;
        }
        
        return dummy.next;
    }
}

Complexity Analysis

  • Time Complexity: O(NK log(NK)) - Where N is average list length, sorting takes O(NK log(NK))
  • Space Complexity: O(N*K) - For storing all values

Approach 2: Merge Two at a Time

Intuition

Merge lists pairwise repeatedly until only one list remains.

Algorithm

  1. Merge first two lists
  2. Merge result with third list
  3. Continue until all lists are merged
java
class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }
}

public class Solution {
    private ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        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;
    }
    
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) return null;
        
        ListNode result = lists[0];
        
        for (int i = 1; i < lists.length; i++) {
            result = mergeTwoLists(result, lists[i]);
        }
        
        return result;
    }
}

Complexity Analysis

  • Time Complexity: O(K * N*K) - Each merge takes O(current length), total K-1 merges
  • Space Complexity: O(1) - Merging in place

Approach 3: Divide and Conquer

Intuition

Merge lists in pairs like merge sort. This reduces the number of comparisons significantly.

Algorithm

  1. Pair up K lists and merge each pair
  2. Repeat until only one list remains
  3. Total log K levels of merging
java
class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }
}

public class Solution {
    private ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        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;
    }
    
    private ListNode mergeKListsHelper(ListNode[] lists, int left, int right) {
        if (left == right) {
            return lists[left];
        }
        
        if (left > right) {
            return null;
        }
        
        int mid = left + (right - left) / 2;
        
        ListNode leftMerged = mergeKListsHelper(lists, left, mid);
        ListNode rightMerged = mergeKListsHelper(lists, mid + 1, right);
        
        return mergeTwoLists(leftMerged, rightMerged);
    }
    
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) return null;
        return mergeKListsHelper(lists, 0, lists.length - 1);
    }
}

Complexity Analysis

  • Time Complexity: O(NK log K) - log K levels, each level processes all NK elements
  • Space Complexity: O(log K) - Recursion stack

Approach 4: Min-Heap (Optimal)

Intuition

Use a min-heap to track the smallest node among the current heads of all lists. Always extract the minimum and advance that list's pointer.

Algorithm

  1. Add head of each list to min-heap
  2. Extract minimum node, add to result
  3. If extracted node has next, add next to heap
  4. Repeat until heap is empty
java
import java.util.*;

class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }
}

public class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) return null;
        
        // Min-heap based on node value
        PriorityQueue<ListNode> minHeap = new PriorityQueue<>(
            (a, b) -> a.val - b.val
        );
        
        // Add head of each list
        for (ListNode list : lists) {
            if (list != null) {
                minHeap.offer(list);
            }
        }
        
        ListNode dummy = new ListNode(0);
        ListNode curr = dummy;
        
        while (!minHeap.isEmpty()) {
            // Extract minimum
            ListNode minNode = minHeap.poll();
            
            curr.next = minNode;
            curr = curr.next;
            
            // Add next node from same list
            if (minNode.next != null) {
                minHeap.offer(minNode.next);
            }
        }
        
        return dummy.next;
    }
}

Complexity Analysis

  • Time Complexity: O(NK log K) - Each of NK nodes is pushed/popped once, each operation is O(log K)
  • Space Complexity: O(K) - Heap stores at most K nodes (one from each list)

Key Takeaways

  1. Brute force ignores the sorted property - inefficient
  2. Sequential merging leads to O(K * N*K) - repeated work on same elements
  3. Divide and conquer achieves O(N*K log K) with O(log K) space
  4. Min-heap is optimal for space - only O(K) extra space
  5. This is LeetCode 23 - a very important interview problem
  6. Heap approach processes each node exactly once
  7. Same technique applies to merging K sorted arrays
  8. For Python, use tuple with index to break ties in heap comparison
Previous
Leetcode reorganize strings
Next
Smallest range in K Lists