题解 | #合并k个已排序的链表#

/**
 * 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) {
      if (lists.size() == 1) {  // 链表长度最小为1
        return lists[1];
      }
      
      return div(lists, 0, lists.size()-1);
    }
  private:
    ListNode* div(std::vector<ListNode *> &lists, int left, int right) {
      if (left > right) {
        return nullptr;
      }
      if (left == right) {
        return lists[left];
      }
      int mid = (left + right) / 2;
      
      return merge(div(lists, left, mid), div(lists, mid + 1, right));
    }
  
    ListNode* merge(ListNode *head1, ListNode *head2) {
      if (head1 == nullptr || head2 == nullptr) {
        return head1 == nullptr ? head2 : head1;
      }
      
      ListNode *head = head1->val < head2->val ? head1 : head2;
      ListNode *list1 = head->next, *list2 = head == head1 ? head2 : head1, *cur_head = head;
      
      while (list1 && list2) {
        cur_head->next = list1->val < list2->val ? list1 : list2;
        cur_head = cur_head->next;
        list1 == cur_head ? (list1 = list1->next) : (list2 = list2->next);
      }
      
      cur_head->next = list1 == nullptr ? list2 : list1;
      
      return head;
    }
};

优先级队列（不写了）直接贴上来

class Solution {
public:
    struct cmp {
    //重载小顶堆比较方式
    bool operator()(ListNode* a, ListNode* b) { 
        return  a->val > b->val;  
    }
};
    ListNode *mergeKLists(vector<ListNode *> &lists) {
        //小顶堆
        priority_queue<ListNode*, vector<ListNode*>, cmp> pq; 
        //遍历所有链表第一个元素
        for(int i = 0; i < lists.size(); i++){ 
            //不为空则加入小顶堆
            if(lists[i] != NULL) 
                pq.push(lists[i]);
        }
        //加一个表头
        ListNode* res = new ListNode(-1); 
        ListNode* head = res;
        //直到小顶堆为空
        while(!pq.empty()){ 
            //取出最小的元素
            ListNode* temp = pq.top(); 
            pq.pop();
            //连接
            head->next = temp; 
            head = head->next;
            //每次取出链表的后一个元素加入小顶堆
            if(temp->next != NULL)
                pq.push(temp->next);
        }
        return res->next;
    }
};