多个有序链表合并排序

https://leetcode.com/articles/merge-k-sorted-list/#

思路

1.最初版代码中每次比较k组中最小的元素，选择最小的那个。最小的那组指针迭代后继续比较。
2.通过优先队列的方法，每次比较的依旧是k个数，但优先队列采用的是最小堆，所以每次插入的时间复杂度为O(logk)，一共要插入的个数为所有元素的个数。时间复杂度为O(nlogk)。
将所有元素按组插入优先队列中时间复杂度为O(nlogn)高于上述方法
3.基础方法merge两个数组。两两merge来减少merge的次数。（此方法未实践）

关于优先队列

struct cmp{
   bool operator()(ListNode * l1,ListNode * l2)
   {
       return l1->val > l2 -> val;
   }
};
priority_queue<ListNode *,vector<ListNode *> ,cmp >q;
push，pop（没有返回值），top

代码

/**
* 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);
       ListNode * now = head;
       int n = lists.size();
       int min = 0;
       int id = 0;
       bool flag  = false;
       while(1){
           flag = false;
           for(int i = 0; i < n; i ++)
           {
               if(lists[i] == NULL)continue;
               if(!flag)
               {
                   min = lists[i] -> val;
                   id = i;
                   flag = true;
               }
               if(lists[i] -> val < min)
               {
                   id = i;
                   min = lists[i] -> val;
               }
           }
           if(flag == false)break;
           ListNode * neww = new ListNode(min);
           lists[id] = lists[id] -> next;
           now -> next = neww;
           now = now -> next;
       }
       return head -> next;
   }
};

/**
* Definition for singly-linked list.
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
struct cmp{
  bool operator()(ListNode * l1,ListNode * l2)
  {
      return l1->val > l2 -> val;
  }
};
class Solution {
  priority_queue<ListNode *,vector<ListNode *> ,cmp >q;
public:
  ListNode* mergeKLists(vector<ListNode*>& lists) {
      ListNode * head = new ListNode(0);
      ListNode * now = head;
      int n = lists.size();
      
      for(int i = 0; i < n; i ++)
      {
          if(lists[i])
          {
              q.push(lists[i]);
          }
      }
      while(!q.empty())
      {
          ListNode *neww = q.top();
          q.pop();
          now ->next = neww;
          now = now -> next;
          if(neww -> next)
          {
              q.push(neww->next);
          }
      }
      return head -> next;
  }
};