23. Merge k Sorted Lists (hard ) !!!!!!!!!!!

You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.

Merge all the linked-lists into one sorted linked-list and return it.

 

Example 1:

Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
Explanation: The linked-lists are:
[
  1->4->5,
  1->3->4,
  2->6
]
merging them into one sorted list:
1->1->2->3->4->4->5->6

Example 2:

Input: lists = []
Output: []

Example 3:

Input: lists = [[]]
Output: []

 

Constraints:

• k == lists.length
• 0 <= k <= 104
• 0 <= lists[i].length <= 500
• -104 <= lists[i][j] <= 104
• lists[i] is sorted in ascending order.
• The sum of lists[i].length will not exceed 104.

A:
------------------第二遍 -------  use priority queue ------ as min heap -------------

/**

* Definition for singly-linked list.

* struct ListNode {

* int val;

* ListNode *next;

* ListNode() : val(0), next(nullptr) {}

* ListNode(int x) : val(x), next(nullptr) {}

* ListNode(int x, ListNode *next) : val(x), next(next) {}

* };

*/

class Solution {

public:

ListNode* mergeKLists(vector<ListNode*>& lists) {

ListNode header;

auto tail = &header;

auto cmp = [](ListNode* a, ListNode* b) { return a->val > b->val; };

priority_queue<ListNode*, vector<ListNode*>, decltype(cmp) > pq;

for(auto p : lists){

if(p)

pq.push(p);

}

while(!pq.empty()){

auto tmp = pq.top();

pq.pop();

tail->next = tmp;

tail = tail->next;

if(tmp->next){

pq.push(tmp->next);

}

}

return header.next;

}

};

Errors:

1: even when adding, we should also check it is NULL pointer.

if(p)

pq.push(p);

---------------------------第一遍-------------Merge every two list---------------

public class Solution {
      public ListNode mergeKLists(ArrayList<ListNode> lists) {
        if (lists == null || lists.size() == 0) {
            return null;
        }
        // every time, find two shortest list, and merge them
        ListNode header = new ListNode(Integer.MIN_VALUE);
        header.next = lists.remove(0);

        while (!lists.isEmpty()) {
            // merge the second onto the first
            ListNode curHeader = new ListNode(0);
            curHeader.next = lists.remove(0);
            // add merge two list
            header = merge2List(header, curHeader);
        }
        return header.next;
    }

    private ListNode merge2List(ListNode header1, ListNode header2) {
        ListNode runner1 = header1;
        while (header2.next != null) {
            // detach first node of header2 list
            ListNode tmp = header2.next;
            header2.next = header2.next.next; // delete tmp node
            // find runner1 , such that runner1.val <
            while (runner1.next != null && runner1.next.val < tmp.val) {
                runner1 = runner1.next;
            }
            tmp.next = runner1.next;
            runner1.next = tmp;
            runner1 = runner1.next; // point to the next possible value
        }
        return header1;
    }
}

其实，网上有个用heap来做的。但是，需要自己动手写comparator，这个正是爷们儿的弱项。需要多写几个。


Mistakes:
1: 检查了输入的null,但是没有检查当 size() == 0的时候的情况
2:  由于merge 的时候，我们用了header 来， 所以返回的时候， 原本的list head 可能已经改变了，所以需要给 mergeTwoList() 一个返回值，并  主动设置 i_{th} position  of the given ArrayList.
3: 当加入到preNode 和 curNode 之间时，  要记得  重新设置 preNode到 curNode之前。  以保持一致。
4: 汗， 加入到尾部的时候，也要重新设置curNode， 郁闷中~~~~~~~~~~总是犯错
                curNode = tmp;

Learned: