23. Merge k Sorted Lists

-----------------------------------------------------------question------------------------------------------------------
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

Example:

Input:
[
  1->4->5,
  1->3->4,
  2->6
]
Output: 1->1->2->3->4->4->5->6

------------------------------------------------------------analyse-----------------------------------------------------
这道题侧重数据结构的运用， 很多时候数据结构看起来比较简单。但是运用的时候却会束手无策。该题目用的结构相当于是一个
单链表的结构，但是将子结构放到一个向量中嵌套，需要灵或调用该结构并比较大小。

这道题我用两个方法来讲分别时间复杂度较高但空间复杂度较低的方法（简单容易理解），以及降低时间复杂度增加空间复杂度
的方法。



------------------------------------------------------------solution----------------------------------------------------

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
 
 ////////////以上为链表的结构
 
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        ListNode *head = new ListNode(0), *cur = head;
        int min = INT_MAX, idx = 0;
        while(true){
            for (int i=0; i<lists.size(); i++){
                if(lists[i] && lists[i]->val < min){
                    min = lists[i] -> val;
                    idx = i; //首先找到头部数值最小的子序列，在向量的第几位
                }
            }
            if(min == INT_MAX){  // 如果序列为空或满足条件则跳出 min == INI_MAX
                break;
            }
            cur->next = lists[idx];
            cur = cur->next;//逐渐相当于新建的ListNode后一位便于添加新的当前子序列的第一个值中的最小值
            lists[idx] = lists[idx]->next;//被调用的子序列的头指向下一个元素便于比较
            min = INT_MAX; //设置条件要是比较完成则满足条件退出循环           
        }
        return head->next;
    }
};


sulution2  priority_queue

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        priority_queue<int, vector<int>, greater<int>>pq;// 加入了greater<int>表示为小顶堆
        for (auto list:lists){
            while(list){
                pq.push(list->val);
                list = list->next;
            }   
        }
        ListNode* head = new ListNode(0);
        //ListNode* head = list;
        while(!pq.empty()){
            head->next = new ListNode(pq.top());
            head = head->next;
            pq.top();
        }  
    return head->next;
    }
};

这个方法和之前一样是个简单方法了 不过简单用了priority_queue   模板申明带3个参数：
priority_queue<Type, Container, Functional>，其中Type 为数据类型，Container为保存数据的容器，
Functional为元素比较方式。
 此处Functional 为greater<int>，表示是一个小顶堆， 出栈先出最小的值
 
在新建一个链表将逐个小的值加入链表


sulution: 大佬写的牛鼻方法


class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
    if(lists.empty()){
        return nullptr;
    }
    
    map<int,int> map;
    for(int i = 0; i < lists.size(); i++){
        ListNode *head = lists[i];
        while(head != nullptr){
            map[head->val]++;
            head = head->next;
        }
    }
    
    ListNode *head = nullptr;
    ListNode *p = nullptr;
    for(auto it = map.begin(); it != map.end(); it++){
        while(it->second != 0){
            if(head == nullptr){
                p = new ListNode(it->first);
                head = p;
                it->second--;
            }else{
                ListNode *temp = new ListNode(it->first);
                p->next = temp;
                p = p->next;
                it->second--;
            }
        }
    }
    return head;
}
};