Merge K Sorted Lists

Problem Statement:

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 the merged linked list.

Example:

Example 1:

Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
Explanation: The linked lists:
[
  1 -> 4 -> 5,
  1 -> 3 -> 4,
  2 -> 6
]
are merged into:
1 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5 -> 6

Example 2:

Input: lists = []
Output: []

Example 3:

Input: lists = [[]]
Output: []

Constraints:

• k == lists.length
• 0 <= k <= 10^4
• 0 <= lists[i].length <= 500
• -10^4 <= lists[i][j] <= 10^4
• The linked lists are sorted in ascending order.
• The sum of all linked list elements will not exceed 10^5.

Solution Explanation:

The problem can be solved using a min-heap (priority queue) to repeatedly extract the smallest element from the heads of the lists and append it to the result.

Approach:

1. Insert the first node of each list into the priority queue (min-heap).
2. Extract the smallest element from the heap and append it to the result list.
3. Insert the next element from the same list into the heap (if it exists).
4. Repeat until all elements are processed.

Solution: Merge K Sorted Lists

To solve the problem efficiently, we can use a min-heap (priority queue) to keep track of the smallest elements across the k sorted linked lists. The idea is to always extract the smallest element, append it to the result, and then move to the next element in the same linked list.

Here’s the step-by-step solution in Java:

Java Solution Using Priority Queue

import java.util.PriorityQueue;

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

public class MergeKSortedLists {

    // Define a comparator for the priority queue to compare ListNode values
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) return null;

        // Priority Queue to hold the smallest elements from each list
        PriorityQueue<ListNode> minHeap = new PriorityQueue<>((a, b) -> a.val - b.val);

        // Add the first node of each list to the priority queue
        for (ListNode list : lists) {
            if (list != null) {
                minHeap.offer(list);
            }
        }

        // Create a dummy node to serve as the head of the merged list
        ListNode dummy = new ListNode(0);
        ListNode current = dummy;

        // Continue until the priority queue is empty
        while (!minHeap.isEmpty()) {
            // Extract the node with the smallest value
            ListNode smallestNode = minHeap.poll();
            current.next = smallestNode;
            current = current.next;

            // If there is a next node in the same list, add it to the priority queue
            if (smallestNode.next != null) {
                minHeap.offer(smallestNode.next);
            }
        }

        // Return the merged list, skipping the dummy node
        return dummy.next;
    }

    // Utility method to print the linked list
    public static void printList(ListNode head) {
        while (head != null) {
            System.out.print(head.val + " -> ");
            head = head.next;
        }
        System.out.println("null");
    }

    public static void main(String[] args) {
        // Example input: [[1,4,5], [1,3,4], [2,6]]
        ListNode list1 = new ListNode(1);
        list1.next = new ListNode(4);
        list1.next.next = new ListNode(5);

        ListNode list2 = new ListNode(1);
        list2.next = new ListNode(3);
        list2.next.next = new ListNode(4);

        ListNode list3 = new ListNode(2);
        list3.next = new ListNode(6);

        ListNode[] lists = {list1, list2, list3};

        MergeKSortedLists solution = new MergeKSortedLists();
        ListNode result = solution.mergeKLists(lists);

        // Print the merged list
        System.out.println("Merged List:");
        printList(result); // Expected Output: 1 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5 -> 6 -> null
    }
}

Explanation:

1. ListNode Class: Represents each node in a singly linked list.
2. PriorityQueue (min-heap): This data structure helps us keep track of the smallest node among all the current heads of the lists.

• A comparator is defined to sort the nodes based on their values.

1. Process:

• Initialize a priority queue and add the first node of each linked list to the queue.
• Extract the smallest node from the queue and append it to the result list.
• If the smallest node has a next node, insert it into the queue.
• Repeat until all nodes are processed.

1. Dummy Node: A dummy node is used to simplify list operations when building the merged list.

Time Complexity:

• O(N log k), where N is the total number of nodes across all lists, and k is the number of linked lists. The heap operations (insert/extract) take O(log k) time, and we perform N insert/extract operations in total.

Space Complexity:

• O(k) for the heap, where k is the number of linked lists stored in the priority queue.