Not Only Algorithm,不仅仅是算法,关注数学、算法、数据结构、程序员笔试面试以及一切涉及计算机编程之美的内容 。。
你的位置:NoAlGo博客 » 题解 » 

Leetcode Merge k Sorted Lists

Leetcode algorithms 第 23 题:Merge k Sorted Lists。

题目

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

解答

k个链表归并。和2链表归并的思想一致,首先使用一个头结点dummy方便处理,然后每次找出k个链表的首元素的最小值,将其移到结果链表中,知道所有k个链表变为空为止。

由于每次寻找k个元素的最小值也比较麻烦,这里使用一个优先队列,本质上是一个最小堆,可以方便地得到k个链表中的最小元素,减少算法的时间复杂度。

具体代码如下:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    struct cmp //优先度咧仿函数
    {
        bool operator()(const ListNode *a, const ListNode *b)
        {
            return a->val > b->val; //需要得到的是最小值,于是这里使用大于关系
        }
    };
    
    ListNode *mergeKLists(vector<ListNode *> &lists) {
        ListNode dummy(-1), *cur = &dummy; //辅助用头结点
        
        priority_queue<ListNode *, vector<ListNode *>, cmp> que; //使用最小堆寻找最小值
        for (auto p = lists.begin(); p != lists.end(); p++)
            if (*p != NULL) //每个链表首元素入队
                que.push(*p); 
        while (!que.empty())
        {
            ListNode *fr = que.top(); que.pop(); //取出当前最小元素
            cur->next = fr, cur = cur->next;
            if (fr->next) que.push(fr->next); //放入该队列下一个元素
        }
        
        return dummy.next;
    }
};
上一篇: 下一篇:

我的博客

NoAlGo头像编程这件小事牵扯到太多的知识,很容易知其然而不知其所以然,但真正了不起的程序员对自己程序的每一个字节都了如指掌,要立足基础理论,努力提升自我的专业修养。

站内搜索

最新评论