【LeetCode】23. 合并K个排序链表（Hard）(Heap / 分治)

• Q23.合并K个排序链表【Hard】

合并 k 个排序链表，返回合并后的排序链表。

说明：请分析和描述算法的复杂度。

样例 0:

输入:

[

  1->4->5,

  1->3->4,

  2->6

]

输出: 1->1->2->3->4->4->5->6

样例 1:

        输入:   [2->4->null,null,-1->null]

        输出:  -1->2->4->null

样例 2:

        输入: [2->6->null,5->null,7->null]

        输出:  2->5->6->7->null

相关题目：839. 合并两个排序的间隔列表791. 合并数字6. 合并排序数组 II4. 丑数 II

486. 合并k个排序数组

// 法1：归并排序 - 写法1（写法2: 两两合并见py法2）
public ListNode mergeKLists_v1(ListNode[] lists) {
    if (lists == null || lists.length == 0)
        return null;
    return mergeHelper(lists, 0, lists.length-1);
}

private ListNode mergeHelper(ListNode[] lists, int start, int end){
    if (start == end)
        return lists[start];
    int mid = start + end >> 1;
    ListNode left = mergeHelper(lists, start, mid);
    ListNode right = mergeHelper(lists, mid+1, end);
    return mergeTwoLists(left, right);
}

private ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(-1);
    ListNode p = dummy;
    while (l1 != null && l2 != null) {
        if (l1.val < l2.val) {
            p.next = l1;
            p = l1; // 指针后移
            l1 = l1.next;
        } else {
            p.next = l2;
            p = l2; // 指针后移
            l2 = l2.next;
        }
    }
    if (l1 != null) p.next = l1;
    if (l2 != null) p.next = l2;
    return dummy.next;
}

// 法2：最小堆minHeap（每次将K个头结点放入堆，pop出的就是最小的元素）
//  - 每次 O(logK) 比较 K个指针求 min, 时间复杂度：O(NlogK)
private Comparator<ListNode> listNodeComparator = 
				new Comparator<ListNode>() {
    @Override
    public int compare(ListNode l1, ListNode l2) {
        return l1.val - l2.val; // 升序 l1 < l2 < ...
    }
};

public ListNode mergeKLists_v2(ListNode[] lists) {
    if (lists == null || lists.length == 0)
        return null;
    PriorityQueue<ListNode> heap = 
		new PriorityQueue<>(lists.length, listNodeComparator);
    for (ListNode listNode : lists){
        if (listNode == null) continue; // 勿漏！！！ 形如:[[]]
        heap.add(listNode); // 加入的只有每个链表的头部
    }

    ListNode dummy = new ListNode(-1);
    ListNode p = dummy;
    while (!heap.isEmpty()) {
        ListNode cur = heap.poll(); // 不是pop！
        p.next = cur;
        p = cur;
        if (cur.next != null)
            heap.add(cur.next); // 每个链表的next
    }
    return dummy.next;
}

法2分析：