Merge k Sorted Lists - Java Solution

1. Introduction

In this post, we address the "Merge k Sorted Lists" problem, a more advanced variation of the classic merge sorted lists challenge. This problem involves merging multiple sorted linked lists into one single sorted linked list. It's a common question in data structures, particularly in understanding how to efficiently combine multiple sorted sequences.

Problem

Given an array of k linked-lists lists, where each linked list is sorted in ascending order, the goal is to merge all the linked lists into one sorted linked list and return it.

Examples:

1. Input: lists = [[1,4,5],[1,3,4],[2,6]]

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

2. Input: lists = []

Output: []

3. Input: lists = [[]]

Output: []

2. Solution Steps

1. Utilize a priority queue (min heap) to efficiently merge the lists.

2. Add the first node of each list to the priority queue.

3. Pop the smallest element from the queue and add it to the merged list.

4. If the popped element has a next node, add that node to the queue.

5. Continue this process until the queue is empty.

6. Return the head of the merged list.

3. Code Program

import java.util.PriorityQueue;

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

public class MergeKSortedLists {
    public static void main(String[] args) {
        // Example use case
        ListNode[] lists = new ListNode[3];
        lists[0] = new ListNode(1);
        lists[0].next = new ListNode(4);
        lists[0].next.next = new ListNode(5);

        lists[1] = new ListNode(1);
        lists[1].next = new ListNode(3);
        lists[1].next.next = new ListNode(4);

        lists[2] = new ListNode(2);
        lists[2].next = new ListNode(6);

        ListNode result = mergeKLists(lists);
        while (result != null) {
            System.out.print(result.val + " ");
            result = result.next;
        }
    }

    // Function to merge k sorted linked lists
    public static ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) return null;

        PriorityQueue<ListNode> queue = new PriorityQueue<>((l1, l2) -> l1.val - l2.val);
        ListNode dummy = new ListNode(0);
        ListNode current = dummy;

        for (ListNode list : lists) {
            if (list != null) {
                queue.add(list);
            }
        }

        while (!queue.isEmpty()) {
            ListNode node = queue.poll();
            current.next = node;
            current = current.next;

            if (node.next != null) {
                queue.add(node.next);
            }
        }

        return dummy.next;
    }
}

Output:

1 1 2 3 4 4 5 6

Explanation:

1. mergeKLists: This function merges k sorted linked lists into a single sorted list.

2. A priority queue is used to determine the smallest node at each step efficiently.

3. The first node of each list (if not null) is added to the queue.

4. The function repeatedly removes the smallest element from the queue and adds it to the merged list, maintaining the sorted order.

5. If the removed node has a next node, that node is added to the queue for future processing.

6. The loop continues until the queue is empty, meaning all nodes have been processed and added to the merged list.

7. The function returns the head of the merged list, starting from the next node of the dummy node, ensuring proper handling of the initial empty node.

8. This approach effectively combines multiple sorted lists while maintaining the overall sorted order, demonstrating the power and efficiency of priority queues.