Merge K Sorted Lists – LeetCode 23 Solution

The LeetCode 23 problem, “Merge K Sorted Lists,” is a classic example that tests your ability to implement optimized algorithms for merging lists. Let’s explore the problem statement, analyze its solutions, and discuss their time and space complexities.

Problem Statement for Merge K Sorted Lists

You are given an array of k linked lists, where each linked list is sorted in ascending order. Your task is to merge all the linked lists into one sorted linked list and return it.

Example

Input:

lists = [[1,4,5],[1,3,4],[2,6]]

Output:

[1,1,2,3,4,4,5,6]

Explanation:
The merged linked list combines all nodes from the input lists in ascending order.

Constraints for Merge K Sorted Lists Problem

• The number of linked lists k can range from 0 to 10^4.
• The length of each linked list can range from 0 to 500.
• Values in each linked list node fall within -10^4 to 10^4.

Approaches to Solve Merge K Sorted Lists Problem

1. Brute Force Solution for Merge K Sorted Lists

A straightforward way to solve this is:

1. Traverse all the nodes from each linked list.
2. Collect the values into an array.
3. Sort the array.
4. Create a new linked list using the sorted values.

Implementation in Java:

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

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

Complexity Analysis:

• Time Complexity: O(Nlog⁡N), where N is the total number of nodes across all lists (sorting dominates).
• Space Complexity: O(N) for storing all nodes.

2. A Min-Heap (Priority Queue) Solution for Merge K Sorted Lists

A more optimized approach involves using a min-heap to keep track of the smallest elements across the lists.

Steps:

1. Push the head of each linked list into the min-heap.
2. Extract the smallest element, append it to the merged list, and push the next node from the same list into the heap.
3. Repeat until the heap is empty.

Implementation in Java:

import java.util.PriorityQueue;

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

public ListNode mergeKLists(ListNode[] lists) {
    PriorityQueue<ListNode> minHeap = new PriorityQueue<>((a, b) -> a.val - b.val);
    
    // Add the head of each linked list to the min-heap
    for (ListNode list : lists) {
        if (list != null) {
            minHeap.add(list);
        }
    }
    
    ListNode dummy = new ListNode(0);
    ListNode current = dummy;
    
    // Process the min-heap
    while (!minHeap.isEmpty()) {
        ListNode smallest = minHeap.poll();
        current.next = smallest;
        current = current.next;
        
        if (smallest.next != null) {
            minHeap.add(smallest.next);
        }
    }
    
    return dummy.next;
}

Complexity Analysis:

• Time Complexity: O(Nlog⁡k), where k is the number of lists, and N is the total number of nodes.
• Space Complexity: O(k) for the heap.

3. Divide and Conquer Solution for Merge K Sorted Lists

In this approach, we repeatedly merge pairs of linked lists using the two-sorted-lists merge technique.

Steps:

1. Pair up linked lists and merge them.
2. Repeat until only one list remains.

Implementation in Java:

public ListNode mergeKLists(ListNode[] lists) {
    if (lists == null || lists.length == 0) return null;
    return mergeLists(lists, 0, lists.length - 1);
}

private ListNode mergeLists(ListNode[] lists, int start, int end) {
    if (start == end) return lists[start];
    int mid = start + (end - start) / 2;
    ListNode left = mergeLists(lists, start, mid);
    ListNode right = mergeLists(lists, mid + 1, end);
    return mergeTwoLists(left, right);
}

private ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(0);
    ListNode current = dummy;
    
    while (l1 != null && l2 != null) {
        if (l1.val < l2.val) {
            current.next = l1;
            l1 = l1.next;
        } else {
            current.next = l2;
            l2 = l2.next;
        }
        current = current.next;
    }
    
    if (l1 != null) current.next = l1;
    if (l2 != null) current.next = l2;
    
    return dummy.next;
}

Complexity Analysis:

• Time Complexity: O(Nlog⁡k), where N is the total number of nodes and k is the number of lists.
• Space Complexity: O(log⁡k) due to recursion.

Which Approach to Choose?

1. Brute Force: Simple to implement but inefficient for large inputs.
2. Min-Heap: Optimal for most practical cases, especially when k is much smaller than N.
3. Divide and Conquer: Performs well when k is very large, leveraging the balanced merging process.

Conclusion

The Merge K Sorted Lists problem is a versatile question that highlights the importance of efficient data structures like heaps and recursive techniques. While the brute force method might work for smaller inputs, the min-heap and divide-and-conquer approaches are better suited for larger datasets.

By understanding these solutions, you not only prepare yourself for interviews but also improve your algorithmic thinking for real-world applications. Start practicing today and master this classic problem!