K個のソート・チェーン・テーブルのマージ--優先キューの解決

0x01.に質問
k個のソートチェーンテーブルをマージし、マージ後のソートチェーンテーブルを返します.入力例:[1->4->5,1->3->4,2->6]出力例:1->1->2->3->4->5->6
この問題は、前の問題のアップグレード版と2つの順序付きチェーンテーブルを統合することです.

C++   ：
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
 C++    ： ListNode* mergeKLists(vector<ListNode*>& lists) 

0x02.簡単な分析
前の問題とは異なり、今回要求されたのはk個のチェーンテーブルのソートであり、2つのチェーンテーブルのソートだけではない.
しかし、基本的な考え方は変わらず、それぞれの中から最小値を出して、結果チェーンテーブルに追加します.
しかし、チェーン時計が多いことを考えると、暴力の取り出しは望ましくないに違いない.
1つの考え方は、複数のチェーンテーブルを最終的に2つのチェーンテーブルの合併に変換することです.これは実は分治の考え方であり、間違いなく可能です.ここでは、より理解しやすい解決策を使用します.
最も暴力的な考え方は、すべてのチェーンテーブルを配列に変換することです.目的は何ですか.順序を簡単にするためです.では、私たちは遍歴するときに順序をつけることができますか.つまり、秩序のある容器に入れることができます.間違いなく、優先キューはできます.私たちは小さなトップスタック、つまり最小値の優先キューを維持することができます.まずノードを優先キューに入れ、取り出すたびに次のノードを優先キューに入れます.優先キューの優先度の関係で、入れたデータは秩序化されます.これにより、キューの先頭から1つの要素を取り出して結果チェーンテーブルに入れればいいのです.
優先キューの助けを借りて、この問題は非常に簡単になり、絶えず入隊して出なければならない限り、このソートプロセスが完了します.
0x03.解決コード–優先キュー

class Solution {
public:
    struct mycomp{
        bool operator()(ListNode* a,ListNode* b){
            return a->val>b->val;
        }    
    };
    ListNode* mergeKLists(vector<ListNode*>& lists) {
          priority_queue<ListNode*, vector<ListNode*>, mycomp> queue;
          for(ListNode*head:lists){
              if(head) queue.push(head);
          }
          ListNode* dummy = new ListNode(-1);
          ListNode* temp = dummy;
          while(!queue.empty()){
              ListNode* p = queue.top();
              queue.pop();
              if(p->next) queue.push(p->next);
              temp->next=p;
              temp=temp->next;
          }
          return dummy->next;
    }
};

class Solution {
	public ListNode mergeKLists(ListNode[] lists) {
		if(lists==null || lists.length==0) {
			return null;
		}
		//     ，          
		PriorityQueue<ListNode> queue = new PriorityQueue(new Comparator<ListNode>() {
			public int compare(ListNode o1, ListNode o2) {
				return (o1.val - o2.val);
			}
		});
		//      ，                 
		for(int i=0;i<lists.length;i++) {
			while(lists[i] != null) {
				queue.add(lists[i]);
				lists[i] = lists[i].next;
			}
		}
		ListNode dummy = new ListNode(-1);
		ListNode head = dummy;
		//         ，           
		while( !queue.isEmpty() ) {
			dummy.next = queue.poll();
			dummy = dummy.next;
		}
		dummy.next = null;
		return head.next;
	}
}

ATFWUS --Writing By 2020–03–23