LeetCode 23: 合并K个排序链表

[guodongxiaren]

https://leetcode-cn.com/problems/merge-k-sorted-lists

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

示例:

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

[guodongxiaren]

解法很多。优先队列和两两归并是最容易想到的。

[guodongxiaren]

C++有现成的优先队列，其实也不难写这道题。

关键是我自己被指针和引用搞崩溃了。

/**
 * 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) {
        auto cmd = [](ListNode* node1, ListNode* node2) {
            return node1->val > node2->val;
        };
        priority_queue<ListNode*, vector<ListNode*>, decltype(cmd)> queue(cmd);

        //for (auto& head: lists) {
            //auto& node = head;   // 会导致超时
        for (auto head: lists) {
            auto node = head;
            if (node) {
                queue.push(node);
            }
        }
        ListNode dummyNode;
        ListNode* node = &dummyNode;
        while (!queue.empty()) {
            //auto& top = queue.top(); // 也会导致超时！应该是死循环了
            auto top = queue.top();
            queue.pop();

            node->next = top;
            node = node->next;
            if (top->next) {
                queue.push(top->next);
            }
        }        
        return dummyNode.next;
    }
};

上述有两处 auto& 会导致超时，应该是死循了。 list和queue的元素本身就是指针：ListNode*的类型。然后再来个&。本质上相当于二级指针了。

[guodongxiaren]

关于优先队列有两个强调：

如果重载 < 默认是大根堆，重载 > 才是小根堆

这和一般sort排序函数的重载直觉相反。

如果用lambda作比较子

注意模板参数内要写decltype。因为模板参数需要类型，auto cmd获得的是一个具体的对象（变量）。 另外如果使用率lambda，再实例化优先队列的时候，lambda表达式要传入构造函数。

        priority_queue<ListNode*, vector<ListNode*>, decltype(cmd)> queue(cmd);

如果用struct则不用！牛逼的C++啊

    struct cmp{  
       bool operator()(ListNode *a, ListNode *b){
          return a->val > b->val;
       };

....
        priority_queue<ListNode*, vector<ListNode*>, cmp> queue;