LeetCode23——Merge K Sorted Lists——Priority Queue

这道题要求合并K个有序链表，题面如下。

合并两个已排序链表是这类问题的一个基本问题，但是当链表数目从2变成K时，如何寻找下一个要插入的结点就变成了一个最重要的问题。可以通过每次遍历每个链表开头的结点来得到(复杂度O(k))当前应该插入的最小值的结点，但是这样的复杂性太高。所以这道题必须引入一个数据结构来帮助我们快速筛选出要插入的下一个结点，我选择的是优先级队列(priority_queue)。当然，因为实现优先级队列的STL底层数据结构是堆，所以与手写一个堆来做效果是一致的。

关于C++中的优先级队列，详细用法可以参考这篇博客priority_queue的用法，学习的重点主要是看如何设定队列中元素的优先级，可以重载运算符<，也可以写一个仿函数ftor，我在本题的代码中使用的是重载运算符。非常重要的一点是，要注意返回值和实际排序的对应关系，它和sort中的直觉是相反的。

所以首先定义一个类QueueElement，其中保存了结点值和对应结点的指针：

    struct QueueElement
    {
        int Val;                                                     
        ListNode* Ptr;                                               
        QueueElement(int V, ListNode* P):Val(V), Ptr(P){}            
        bool operator < (const QueueElement& Other) const            
        {
            return Val > Other.Val;									
        } 
    };

随后定义一个关于QueueElement的优先级队列，这个队列会替我们管理当前的结点序列，保证top()函数会返回当前的最小结点。
完整代码如下：

class Solution {
    
    struct QueueElement
    {
        int Val;                                                     
        ListNode* Ptr;                                               
        QueueElement(int V, ListNode* P):Val(V), Ptr(P){}            
        bool operator < (const QueueElement& Other) const            
        {
            return Val > Other.Val;
        } 
    };

    
    ListNode* mergeNode(ListNode*& Res, ListNode* Node)
    {
        Res->next = Node;
        Res = Node;
        return Res->next;           
    }

public:
    ListNode* mergeKLists(vector& lists) {
        
        ListNode* DummyNode = new ListNode(-1);
        ListNode* Present = DummyNode;

        
        priority_queue Q;

        
        for(int i = 0 ; i < lists.size() ; ++i)
        {
            if(lists[i])
            {
                QueueElement Temp(lists[i]->val, lists[i]);
                Q.push(Temp);
            }
           
        }
           
        while(!Q.empty())
        {
            
            QueueElement Front = Q.top();
            Q.pop();

            
            ListNode* NewHead = mergeNode(Present, Front.Ptr);

            if(NewHead)     
            {
                
                QueueElement Temp(NewHead->val, NewHead);
                Q.push(Temp);
            }
                
        }

        return DummyNode->next;
    }
};