Merge k Sorted Lists

1package pkg5leetcode.blind75;2 3/*4 * Merge k Sorted Lists | LC 235 * APPROACH: Min-heap of list heads by value.6 * COMPLEXITY: Time O(N log k), Space O(k)7 */8import java.util.*;9 10public class blind75_LC23MergeKSortedLists {11    /** Same shape as pkg5leetcode/common/ListNode.java (nested for single-file runs). */12 13    static class ListNode {14        int val;15        ListNode next;16        ListNode(int val) { this.val = val; }17    }18 19    static ListNode mergeKLists(ListNode[] lists) {20        PriorityQueue<ListNode> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a.val));21        for (ListNode node : lists) if (node != null) pq.add(node);22        ListNode dummy = new ListNode(0), tail = dummy;23        while (!pq.isEmpty()) {24            ListNode cur = pq.poll();25            tail.next = cur;26            tail = cur;27            if (cur.next != null) pq.add(cur.next);28        }29        return dummy.next;30    }31 32    static ListNode of(int... vals) {33        ListNode dummy = new ListNode(0), cur = dummy;34        for (int v : vals) { cur.next = new ListNode(v); cur = cur.next; }35        return dummy.next;36    }37 38    static int[] toArray(ListNode head) {39        List<Integer> list = new ArrayList<>();40        while (head != null) { list.add(head.val); head = head.next; }41        return list.stream().mapToInt(Integer::intValue).toArray();42    }43 44    public static void main(String[] args) {45        ListNode[] lists = {of(1, 4, 5), of(1, 3, 4), of(2, 6)};46        check(Arrays.equals(toArray(mergeKLists(lists)), new int[]{1, 1, 2, 3, 4, 4, 5, 6}), "case1");47        check(mergeKLists(new ListNode[]{}) == null, "case2");48        System.out.println("all tests passed");49    }50 51    static void check(boolean cond, String name) {52        if (!cond) throw new AssertionError("FAILED: " + name);53        System.out.println("  PASS " + name);54    }55}