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 是这些链表的节点总数。