LeetCode 23: Merge k Sorted Lists

OG: https://leetcode.com/problems/merge-k-sorted-lists/description/

import java.util.*;

/**
 * LeetCode 23: Merge k Sorted Lists
 * 
 * Problem: Merge k sorted linked lists and return it as one sorted list.
 * 
 * Example:
 * Input: lists = [[1,4,5],[1,3,4],[2,6]]
 * Output: [1,1,2,3,4,4,5,6]
 * 
 * Approaches implemented:
 * 1. Priority Queue (Min Heap) - O(N log k)
 * 2. Divide and Conquer - O(N log k)
 * 3. Sequential Merge - O(kN) [baseline for comparison]
 * 
 * where:
 * - N is total number of nodes across all lists
 * - k is number of linked lists
 */
public class MergeKSortedLists {

    /**
     * Definition for singly-linked list.
     */
    public static class ListNode {
        int val;
        ListNode next;
        ListNode(int x) { val = x; }
        ListNode(int x, ListNode next) { this.val = x; this.next = next; }
    }

    /**
     * Solution using Priority Queue (Min Heap)
     * 
     * Time Complexity: O(N log k)
     * - Each node is added/removed from heap once
     * - Heap operations cost O(log k)
     * - Total nodes = N
     * 
     * Space Complexity: O(k)
     * - Priority queue holds at most k nodes
     * 
     * @param lists Array of sorted linked lists
     * @return Merged sorted linked list
     */
    public ListNode mergeKListsPQ(ListNode[] lists) {
        if (lists == null || lists.length == 0) return null;

        // Create min heap comparing nodes by value
        PriorityQueue<ListNode> pq = new PriorityQueue<>((a, b) -> a.val - b.val);

        // Add first node from each list
        for (ListNode list : lists) {
            if (list != null) {
                pq.offer(list);
            }
        }

        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;

        // Process nodes from heap
        while (!pq.isEmpty()) {
            ListNode node = pq.poll();
            tail.next = node;
            tail = tail.next;

            if (node.next != null) {
                pq.offer(node.next);
            }
        }

        return dummy.next;
    }

    /**
     * Solution using Divide and Conquer
     * 
     * Time Complexity: O(N log k)
     * - Log k levels of merging
     * - Each level processes N nodes total
     * 
     * Space Complexity: O(1) extra space
     * - Only uses recursion stack
     * 
     * @param lists Array of sorted linked lists
     * @return Merged sorted linked list
     */
    public ListNode mergeKListsDC(ListNode[] lists) {
        if (lists == null || lists.length == 0) return null;
        return mergeDC(lists, 0, lists.length - 1);
    }

    private ListNode mergeDC(ListNode[] lists, int start, int end) {
        if (start == end) {
            return lists[start];
        }
        if (start + 1 == end) {
            return merge2Lists(lists[start], lists[end]);
        }

        int mid = start + (end - start) / 2;
        ListNode left = mergeDC(lists, start, mid);
        ListNode right = mergeDC(lists, mid + 1, end);
        return merge2Lists(left, right);
    }

    /**
     * Solution using Sequential Merging (baseline)
     * 
     * Time Complexity: O(kN)
     * - Merges lists one by one
     * - Not optimal but simple to understand
     * 
     * Space Complexity: O(1) extra space
     * 
     * @param lists Array of sorted linked lists
     * @return Merged sorted linked list
     */
    public ListNode mergeKListsSequential(ListNode[] lists) {
        if (lists == null || lists.length == 0) return null;

        ListNode result = lists[0];
        for (int i = 1; i < lists.length; i++) {
            result = merge2Lists(result, lists[i]);
        }
        return result;
    }

    /**
     * Helper method to merge two sorted lists
     */
    private ListNode merge2Lists(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;

        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                tail.next = l1;
                l1 = l1.next;
            } else {
                tail.next = l2;
                l2 = l2.next;
            }
            tail = tail.next;
        }

        tail.next = (l1 != null) ? l1 : l2;
        return dummy.next;
    }

    /**
     * Helper method to create linked list from array
     */
    private static ListNode createList(int[] arr) {
        if (arr == null || arr.length == 0) return null;

        ListNode dummy = new ListNode(0);
        ListNode current = dummy;
        for (int val : arr) {
            current.next = new ListNode(val);
            current = current.next;
        }
        return dummy.next;
    }

    /**
     * Helper method to convert linked list to string
     */
    private static String listToString(ListNode head) {
        StringBuilder sb = new StringBuilder();
        sb.append("[");
        while (head != null) {
            sb.append(head.val);
            if (head.next != null) {
                sb.append(",");
            }
            head = head.next;
        }
        sb.append("]");
        return sb.toString();
    }

    public static void main(String[] args) {
        MergeKSortedLists solution = new MergeKSortedLists();

        // Test cases
        int[][][] testCases = {
            {{1,4,5}, {1,3,4}, {2,6}},                    // Standard case
            {{1}, {2}, {3}},                              // Single elements
            {{1,2,3}, {4,5,6}, {7,8,9}},                 // No interleaving
            {{1,1,1}, {1,1,1}, {1,1,1}},                 // All same values
            {{}, {}, {}},                                 // Empty lists
            {{-1,1}, {-2,2}, {-3,3}},                    // Negative numbers
            {{1,4,5}, {1,3,4}, {2,6}, {1,7}, {2,8}},    // More than 3 lists
            {{1,2,3,4,5,6,7,8,9,10}},                    // Single long list
            {},                                           // Empty array
            {{1,2}, {}, {3,4}},                          // Some empty lists
        };

        String[] testNames = {
            "Standard case",
            "Single elements",
            "No interleaving needed",
            "All same values",
            "Empty lists",
            "Negative numbers",
            "More than 3 lists",
            "Single long list",
            "Empty array",
            "Some empty lists"
        };

        for (int i = 0; i < testCases.length; i++) {
            test(solution, testCases[i], testNames[i]);
        }
    }

    private static void test(MergeKSortedLists solution, int[][] lists, String testName) {
        System.out.println("\nTest: " + testName);

        // Convert input arrays to ListNodes
        ListNode[] inputLists = new ListNode[lists.length];
        System.out.println("Input lists:");
        for (int i = 0; i < lists.length; i++) {
            inputLists[i] = createList(lists[i]);
            System.out.println("  " + listToString(inputLists[i]));
        }

        // Test all three approaches
        ListNode[] inputs = new ListNode[lists.length];

        // Priority Queue approach
        System.arraycopy(inputLists, 0, inputs, 0, lists.length);
        ListNode resultPQ = solution.mergeKListsPQ(inputs);
        System.out.println("Priority Queue result: " + listToString(resultPQ));

        // Divide and Conquer approach
        System.arraycopy(inputLists, 0, inputs, 0, lists.length);
        ListNode resultDC = solution.mergeKListsDC(inputs);
        System.out.println("Divide & Conquer result: " + listToString(resultDC));

        // Sequential approach
        System.arraycopy(inputLists, 0, inputs, 0, lists.length);
        ListNode resultSeq = solution.mergeKListsSequential(inputs);
        System.out.println("Sequential result: " + listToString(resultSeq));

        // Verify all approaches give same result
        boolean match = listToString(resultPQ).equals(listToString(resultDC)) &&
                       listToString(resultDC).equals(listToString(resultSeq));
        System.out.println("All solutions match: " + match);

        // Verify result is sorted
        boolean isSorted = isSorted(resultPQ);
        System.out.println("Result is sorted: " + isSorted);
    }

    /**
     * Helper method to verify list is sorted
     */
    private static boolean isSorted(ListNode head) {
        if (head == null || head.next == null) return true;

        ListNode current = head;
        while (current.next != null) {
            if (current.val > current.next.val) {
                return false;
            }
            current = current.next;
        }
        return true;
    }
}