23.Merge k Sorted Lists (H)

1.Description(Medium)

Merge_k_sorted linked lists and return it as one sorted list.

Analyze and describe its complexity.

Example

Given lists:

[
  2->4->null,
  null,
  -1->null
],

return-1->2->4->null.

2.Code

如果一共n个node, k个linkedlist,那么所有解法的复杂度都是O(nlogk).

Solution 1: 谁小谁出列。

1>找到K个中的最小-----找一个Data Stucture collection中找最小，删除，加入---Heap---PriorityQueue（本质是Heap）

Add(O(logk))->push

Remove(O(logk))->popMin / popMax

peek(O(1))->只看质不pop

2>最小的出列加入新的List(新的linkedlist用dummy)

3>下一个点顶上来（无就扔掉）

public class Solution_104 {

    /**
     * @param lists: a list of ListNode
     * @return: The head of one sorted list.
     */

    class ListNodeComparator implements Comparator<ListNode>{
        @Override
        public int compare(ListNode l1,ListNode l2){
            return l1.val-l2.val;
        }

    }
    public ListNode mergeKLists(List<ListNode> lists){

        if(lists==null || lists.size()==0){
            return null;
        }
        Comparator<ListNode> comparator=new ListNodeComparator();
        PriorityQueue<ListNode> heap=new PriorityQueue<ListNode>(lists.size(),comparator);
        //get the first element of each list
        for(int i=0;i<lists.size();i++){
            if(lists.get(i)!=null){
                heap.add(lists.get(i));
            }
        }

        ListNode dummy=new ListNode(0);
        ListNode temp=dummy;
        while(!heap.isEmpty()){
            ListNode currentMin=heap.poll();
            temp.next=currentMin;          
            if(currentMin.next!=null){
                heap.add(currentMin.next);
            }
            //equal to temp=temp.next;
            temp=currentMin;
        }
        return dummy.next;       
    }

}

Version 2:

合并 k 个有序链表的逻辑类似合并两个有序链表，难点在于，如何快速得到 k 个节点中的最小节点，接到结果链表上？

这里我们就要用到 优先级队列（二叉堆） 这种数据结构，把链表节点放入一个最小堆，就可以每次获得 k 个节点中的最小节点：

ListNode mergeKLists(ListNode[] lists) {
    if (lists.length == 0) return null;
    // 虚拟头结点
    ListNode dummy = new ListNode(-1);
    ListNode p = dummy;
    // 优先级队列，最小堆
    PriorityQueue<ListNode> pq = new PriorityQueue<>(
        lists.length, (a, b)->(a.val - b.val));
    // 将 k 个链表的头结点加入最小堆
    for (ListNode head : lists) {
        if (head != null)
            pq.add(head);
    }

    while (!pq.isEmpty()) {
        // 获取最小节点，接到结果链表中
        ListNode node = pq.poll();
        p.next = node;
        if (node.next != null) {
            pq.add(node.next);
        }
        // p 指针不断前进
        p = p.next;
    }
    return dummy.next;
}

这个算法是面试常考题，它的时间复杂度是多少呢？

优先队列 pq 中的元素个数最多是 k，所以一次 poll 或者 add 方法的时间复杂度是 O(logk)；所有的链表节点都会被加入和弹出 pq，所以算法整体的时间复杂度是 O(Nlogk)，其中 k 是链表的条数，N 是这些链表的节点总数。

Version 3 (Divide Conquer algo):

https://labuladong.online/algo/essential-technique/divide-and-conquer/#%E6%80%BB%E7%BB%93

// 定义：合并 lists[start..end] 为一个有序链表
ListNode mergeKLists3(ListNode[] lists, int start, int end) {
    if (start == end) {
        return lists[start];
    }

    int mid = start + (end - start) / 2;
    // 合并左半边 lists[start..mid] 为一个有序链表
    ListNode left = mergeKLists3(lists, start, mid);

    // 合并右半边 lists[mid+1..end] 为一个有序链表
    ListNode right = mergeKLists3(lists, mid + 1, end);

    // 合并左右两个有序链表
    return mergeTwoLists(left, right);
}

整棵递归树的形态为一棵平衡二叉树，高度是 O(log⁡k); 这个算法中，每条链表需要被遍历（合并）的次数是树的高度，也就是 O(log⁡k)

时空复杂度分析

该算法的时间复杂度相当于是把 kk 条链表分别遍历 O(log⁡k)O(logk) 次。

那么假设 kk 条链表的元素总数是 NN，该算法的时间复杂度就是 O(Nlog⁡k)O(Nlogk)，和 单链表双指针技巧汇总 中介绍的优先级队列解法相同。

再来看空间复杂度，该算法的空间复杂度只有递归树堆栈的开销，也就是 O(log⁡k)O(logk)，要优于优先级队列解法的 O(k)O(k)。

分治思想在递归算法中是广泛存在的，甚至一些非递归算法，都可以强行改写成分治递归的形式，但并不是所有算法都能用分治思想提升效率。

那为什么有些算法可以通过分治思想来优化时间复杂度呢？

把递归算法抽象成递归树，如果递归树节点的时间复杂度和树的深度相关，那么使用分治思想对问题进行二分，就可以使递归树尽可能平衡，进而优化总的时间复杂度。

反之，如果递归树节点的时间复杂度和树的深度无关，那么使用分治思想就没有意义，反而可能引入额外的空间复杂度。

本文的两个例子中，getSum 函数即便改为递归形式，每个递归节点做的事情无非就是一些加减运算，所以递归节点的时间复杂度总是 O(1)O(1)，和树的深度无关，所以分治思想不起作用。

而 mergeKLists 函数中，每个递归节点都需要合并两个链表，这两个链表是子节点返回的，其长度和递归树的高度相关，所以使用分治思想可以优化时间复杂度。

你看，说了半天，本质上又回到二叉树的遍历了。所以我说了一万遍，二叉树非常非常重要，把二叉树玩明白，算法简直不要太简单。