23. Merge k Sorted Lists

二刷 06/2022

Version #1 Priority Queue

注意ListNode是不comparable的，要传comparator进minHeap里面

Time - K lists, average N length, O(NKlogK)

Space - O(K)

/**

 * Definition for singly-linked list.

 * public class ListNode {

 *     int val;

 *     ListNode next;

 *     ListNode() {}

 *     ListNode(int val) { this.val = val; }

 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }

 * }

 */

class Solution {

    public ListNode mergeKLists(ListNode[] lists) {

        ListNode head = new ListNode(0);

        ListNode prev = head;

        Queue<ListNode> minHeap = new PriorityQueue<>((a, b) -> Integer.compare(a.val, b.val));

        for (ListNode list : lists) {

            if (list != null) {

                minHeap.offer(list);

            }

        }

        while (!minHeap.isEmpty()) {

            ListNode curr = minHeap.poll();

            prev.next = curr;

            prev = prev.next;

            if (curr.next != null) {

                minHeap.offer(curr.next);

            }

        }

        return head.next;

    }

}

一刷

k - #lists
n - average #nodes in every list
Time O(nklogk)
Space O(k)
54.05%

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) return null;
        //Min heap
        ListNode dummy = new ListNode(0);
        PriorityQueue<ListNode> pq = new PriorityQueue<>(lists.length, new Comparator<ListNode>() {
            @Override
            public int compare(ListNode node1, ListNode node2) {
                return node1.val - node2.val;
            }
        });
        for (ListNode head : lists) {
            if (head != null) pq.offer(head);
        }
        ListNode curr = dummy;
        ListNode temp;
        while (!pq.isEmpty()) {
            temp = pq.poll();
            curr.next = temp;
            curr = curr.next;
            if (temp.next != null) pq.add(temp.next);
        }
        curr.next = null;
        return dummy.next;
    }
}