September 16, 2019

23. Merge k Sorted Lists

链表长度为 n; k 个链表

Sol 0. Interative

两两比较。Time Complexity: O(k^2*n)

Sol 1. Priority Queue (Min Heap)

Time Complexity: O(nklogk), 总共出入 nk 元素到 pq 里，每个元素 insert 的时间复杂度为 O(logk)，pop 的时间复杂度为 O(1)
Space Complexity: O(k) + O(kn), O(k) 为 pq 的 size，O(kn) 为返回链表的 size

注意：

自定义 comparator
!!!!! 特别注意处理这个edge case:[[]]

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        int l = lists.length;
        if (l == 0) return null; // pay attention to corner case here.
        PriorityQueue<ListNode> minHeap = new PriorityQueue<ListNode>(l, new Comparator<ListNode>(){
            @Override
            public int compare(ListNode l1, ListNode l2) {
                return l1.val - l2.val; // min heap;
            }
        });
        
        ListNode dummy = new ListNode(0);
        ListNode cur = dummy;
        
        for (ListNode node : lists) {
            if (node != null) { // important!! pay attention to corner case here.
                minHeap.offer(node);
            }
        }
        
        while (!minHeap.isEmpty()) {
            cur.next = minHeap.poll();
            if (cur.next.next != null) {
                minHeap.offer(cur.next.next);
            }
            cur = cur.next;
        }
        
        return dummy.next;
    }
}

Sol 2. Divide and Conquer (Binary Reduction)

Merge Sort 思想, reuse 21. Merge Two Sorted Lists

Time Complexity: O(nklogk): 每一层 nk 时间，merge sort 总共 logk 层
Space Complexity: O(logk) -> O(1)

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists.length == 0) {
            return null;
        }
        return mergeKLists(lists, 0, lists.length - 1);
    }
    
    private ListNode mergeKLists(ListNode[] lists, int left, int right) {
        if (left > right) {
            return null;
        }
        if (left == right) {
            return lists[left];
        }
        if (left + 1 == right) {
            return mergeTwoLists(lists[left], lists[right]);
        }
        int mid = left + (right - left) / 2;
        ListNode l1 = mergeKLists(lists, left, mid);
        ListNode l2 = mergeKLists(lists, mid + 1, right);
        return mergeTwoLists(l1, l2);
    }
    
    private ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        }
        if (l2 == null) {
            return l1;
        }
        if (l1.val < l2.val) {
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        } else {
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }
    }
}