23.合并K个排序链表.md

题目描述：合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。

eg:

示例:

输入:
[
  1->4->5,
  1->3->4,
  2->6
]
输出: 1->1->2->3->4->4->5->6

思路描述：首先合并两个排序链表，时间复杂度为O(n)，合并两个链表就是逐个比较两个链表中的元素，比如

  1->4->5,
  1->3->4

先比较第一个元素，list1和list2一样，这里把1加入链表，指针前进一步指向3，再进行比较，1<3，把1加入链表，指针前进一步指向4....，所需要的时间是线性的。

如果遍历一遍，逐个合并一下，时间复杂度为O(n^2)

但是超时了。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2){
       if (!list1) {
            return list2;
        } else if (!list2) {
            return list1;
        } else if (list1->val < list2->val) {
            list1->next = mergeTwoLists(list1->next, list2);
            return list1;
        } else {
            list2->next = mergeTwoLists(list1, list2->next);
            return list2;
        }
    }
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if(lists.size() == 0) return NULL;
        ListNode* ans = lists[0];
        for(int i = 1; i < lists.size(); i ++){
            ans = mergeTwoLists(ans, lists[i]);
        }
        return ans;
    }
};

我们可以使用分治法进行优化，就是把链表数组分成两部分依次merge，最后再把左右两部分进行merge，这个也是比较容易想到的。因为昨天求逆序对也可以使用到分治的思想，所以我觉得这是一个很重要的东西，和dp一样都很常用。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2){
       if (!list1) {
            return list2;
        } else if (!list2) {
            return list1;
        } else if (list1->val < list2->val) {
            list1->next = mergeTwoLists(list1->next, list2);
            return list1;
        } else {
            list2->next = mergeTwoLists(list1, list2->next);
            return list2;
        }
    }
    ListNode* merge(vector <ListNode*> &lists, int l, int r) {
        if (l == r) return lists[l];
        if (l > r) return NULL;
        int mid = (l + r)/2;
        return mergeTwoLists(merge(lists, l, mid), merge(lists, mid + 1, r));
    }
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        return merge(lists, 0, lists.size() - 1);
    }
};

官方题解给了一个使用优先队列的思路，特别巧妙，

首先优先队列是排好序的队列，可以由最小/最大堆实现，所以插入操作的时间复杂度是O(lgn)。

我们先把k个链表的第一个元素插入进去，重构一下小于号，按照val值进行排序。然后队列头部就是值最小的节点，然后把值最小的节点出队，入队值最小的节点的下一个节点，以此类推。如

 1->4->5,
 1->3->4,
 2->6

先入队[1,1,2]，1出队，插入4 -> [1,2,4]，

然后1出队，3入队 -> [3,4,6]

然后3出队，4入队 -> [4,4,6]....

把出队的数字以此链接起来形成链表

其中两个const其实蛮重要的，参数const表明不可以修改rhs引用的对象 函数名后面const表明不能修改其他数据成员，或者调用了其它非const成员函数

class Solution {
public:
    struct Status {
        int val;
        ListNode *ptr;
        bool operator < (const Status &rhs) const {
            return val > rhs.val;
        }
    };

    priority_queue <Status> q;

    ListNode* mergeKLists(vector<ListNode*>& lists) {
        for (auto node: lists) {
            if (node) q.push({node->val, node});
        }
        ListNode head, *tail = &head;
        while (!q.empty()) {
            auto f = q.top(); q.pop();
            tail->next = f.ptr; 
            tail = tail->next;
            if (f.ptr->next) q.push({f.ptr->next->val, f.ptr->next});
        }
        return head.next;
    }
};