LeetCode 23

一、问题描述

Description:

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

合并 k 个有序链表。

二、解题报告

解法一：两两合并

由于前面刚刚做过《LeetCode 21 - Merge Two Sorted Lists》，看到这个题的第一反应就是两两合并，还可以直接调用mergeTwoLists()。

class Solution {
public:
    /**
     * 合并两个有序链表
     */
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode* head = new ListNode(0);
        ListNode* p = head;
        while(l1!=NULL && l2!=NULL) {
            if(l1->val < l2->val) {
                p->next = l1;
                l1 = l1->next;
            }
            else {
                p->next = l2;
                l2 = l2->next;
            }
            p = p->next;
            p->next = NULL;
        }

        if(l1!=NULL)
            p->next = l1;
        if(l2!=NULL)
            p->next = l2;

        return head->next;
    }

    /**
     * 合并k个有序链表：两两合并，直到最终变成一个。
     */
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if(lists.empty())
            return NULL;
        ListNode* node = lists[0]; 
        for(int i=1; i<lists.size(); ++i)
            node = mergeTwoLists(node, lists[i]);

        return node;
    }
};

这种方法超时了！！！

解法二：堆

我们知道对于一个大根堆/小根堆，堆顶元素就是最大/最小值。本解法使用堆就是为了利用它的这个性质，思路就是：

首先把 k 个链表的首节点看作一个集合，对其建堆；
然后取出堆顶的节点，链接到结果链表上；
将取出节点的下一个节点入堆，直到所有链表都完成为止。

这里我们直接使用 C++ STL 的heap算法，它提供了三个主要的操作：

make_heap()：将一段现有的数据转化为一个堆，默认创建 max heap。
push_heap()：这个方法其实就是执行一个向上调整的操作。所以在向堆中插入元素时，必须先将新元素插入到容器的尾部，再对该容器执行push_heap作调整以保持堆的性质。
pop_heap()：这个方法不会移除堆顶元素，只是将堆顶元素转移到容器的尾部，所以在pop_heap后通常还要执行相应容器的 pop 方法作移除。

 class cmp {
 public:
     bool operator()(ListNode* p1, ListNode* p2) const {
        return p1->val > p2->val;
     }
 }; 

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        vector<ListNode*>::iterator beg = lists.begin();
        for( ; beg!=lists.end(); ) {                        // 先移除lists中的空链表
            if(*beg == NULL)
                beg = lists.erase(beg);
            else
                ++beg;
        }
        if(lists.empty())                                   // 如果lists为空
            return NULL;

        make_heap(lists.begin(), lists.end(), cmp());       // 建小根堆
        ListNode* head = new ListNode(0);
        ListNode* p = head;
        while(!lists.empty()) {
            p->next = lists.front();                        // 第一个结点就是堆的根节点
            p = p->next;
            pop_heap(lists.begin(),lists.end(), cmp());     // pop操作将堆的根节点放到容器尾部
            lists.pop_back();                               // 移除之
            if(p->next != NULL) {
                lists.push_back(p->next);                   // 先将新元素插入容器尾部
                push_heap(lists.begin(),lists.end(),cmp()); // push_heap操作进行调整
            }
        }
        return head->next;
    }
};

注意，在使用自定义的比较类（comparator）时，make_heap()、push_heap()、pop_heap()要保持一致。

解法三：优先级队列

C++ STL 还提供了一个priority_queue（优先级队列），顾名思义，它是一个拥有权值观念的队列。

它是队列，所以只能在底端加入元素，从顶端取出元素。
它带有权值观念，所以其中的元素并非依照 push 的次序排列，而是依照权值排列，每次 pop 出权值最高的元素。

priority_queue其实就是调用上面讲到的make_heap()、push_heap()、pop_heap()实现的，所以它的底层就是基于heap。只不过经过封装以后，使用更加方便了。

 class cmp {
 public:
     bool operator()(ListNode* p1, ListNode* p2) const {
        return p1->val > p2->val;
     }
 }; 

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        vector<ListNode*>::iterator beg = lists.begin();
        for( ; beg!=lists.end(); ) {    // 先移除lists中的空链表
            if(*beg == NULL)
                beg = lists.erase(beg);
            else
                ++beg;
        }

        if(lists.empty())               // 如果为空，返回NULL
            return NULL;

        priority_queue<ListNode*,vector<ListNode*>,cmp> q(lists.begin(), lists.end());  // 优先级队列
        ListNode* head = new ListNode(0);
        ListNode* p = head;
        while(!q.empty()) {
            p->next = q.top();
            p = p->next;
            q.pop();
            if(p->next != NULL)
                q.push(p->next);
        }
        return head->next;
    }
};

LeetCode答案源代码：https://github.com/SongLee24/LeetCode