Leetcode 23. 合并K个升序链表

三种方法:

优先级队列(最小堆)

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    struct Cmp{
        bool operator()(ListNode*a,ListNode*b){
            return a->val > b->val;
        }
    };
    ListNode* mergeKLists(vector<ListNode*>& lists) {

        if(lists.size() == 0) 
            return NULL;
        ListNode* dummy = new ListNode(-1);
        ListNode* p = dummy;
        
        //利用二叉堆的性质 最小堆 优先级队列
        //堆构造好之后就可以直接使用了
        priority_queue <ListNode*,vector<ListNode*>,Cmp> heap;

        //默认是最大堆 自己修改最小堆
        //第一个参数:堆中节点数据类型
        //第二个参数 堆使用的数据结构
        //第三个参数 bool值一般指比较大小 返回大于说明大的值往队列后面扔

        //构造最小堆 传入元素
        for(ListNode*x:lists)
        {
            while(x)
            {
                heap.push(x);
                x = x->next;
            }
        }
        while(!heap.empty())
        {
            int y = heap.top()->val;
            heap.pop();
            p->next = new ListNode(y);
            p = p->next;
        }
        return dummy->next;
    }
};

两两比较
分治

参考:
https://www.cnblogs.com/lailailai/p/3759825.html
leetcode

上一篇:JQuery Easy Ui (Tree树)详解(转)


下一篇:堆排序(Heap Sort)