23. Merge k Sorted Lists

My Solution (BF)

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        int n = lists.length;
        ListNode dummy = new ListNode(Integer.MIN_VALUE);
        ListNode current = dummy;

        while (true) {
            int minIndex = -1;
            int minVal = Integer.MAX_VALUE;

            for (int i = 0; i < n; i++) {
                if (lists[i] != null && lists[i].val < minVal) {
                    minVal = lists[i].val;
                    minIndex = i;
                }
            }

            if (minIndex == -1) break; // all empty, finish

            current.next = lists[minIndex];
            current = current.next;
            lists[minIndex] = lists[minIndex].next;
        }

        return dummy.next;
    }
}

Remarks.

1. TC: $O(n*k)$, SC: $O(1)$

Priority Queue

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        // Custom comparator: order nodes by their val in ascending order
        PriorityQueue<ListNode> minHeap = new PriorityQueue<>(
            (a, b) -> Integer.compare(a.val, b.val)
        );

        // Initialize: add the head of each list to the heap
        for (ListNode node : lists) {
            if (node != null) {
                minHeap.offer(node);
            }
        }

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

        // Process the heap: always attach the smallest node to the result list
        while (!minHeap.isEmpty()) {
            ListNode minNode = minHeap.poll();
            current.next = minNode;
            current = current.next;

            // If the extracted node has a next node, add it to the heap
            if (minNode.next != null) {
                minHeap.offer(minNode.next);
            }
        }

        return dummy.next;
    }
}

Remarks:

1. The heap does the comparison and sorting;
2. heap.offer() puts elements into the heap
3. heap.poll() get the one at the top of the heap
4. TC: $n \log k$

Divide & Conquer

public class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) {
            return null;
        }

        List<ListNode> listNodes = new ArrayList<>();
        for (ListNode node : lists) {
            listNodes.add(node);
        }

        while (listNodes.size() > 1) {
            List<ListNode> mergedLists = new ArrayList<>();
            for (int i = 0; i < listNodes.size(); i += 2) {
                ListNode l1 = listNodes.get(i);
                ListNode l2 = (i + 1) < listNodes.size() ? listNodes.get(i + 1) : null;
                mergedLists.add(mergeList(l1, l2));
            }
            listNodes=mergedLists;
        }
        return listNodes.get(0);
    }

    // same as merge sort's 
    private ListNode mergeList(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode();
        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;
        }
        if (l1 != null) {
            tail.next = l1;
        }
        if (l2 != null) {
            tail.next = l2;
        }
        return dummy.next;
    }
}

Remarks:

1. TC: $O(n\log k)$
2. mergeList same as No. 21