题目链接

原题点击此处

思路

  • 用优先队列存储节点指针,并自定义按降序排序
  • 初始时将k个链表头存入,每次取堆顶,并让取出的指针指向后面,如果指针不为空的话,就push进堆中
  • 时间复杂度O(n * log(k)) n是所有元素,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) {}
 * };
 */

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

class Solution {
public:
    priority_queue<ListNode *, vector<ListNode *>, cmp> q;
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        ListNode *dummynode = new ListNode(-1);
        ListNode *pre = dummynode;
        for (int i = 0; i < lists.size(); i++) {
            if (lists[i]) {
                q.push(lists[i]);
            }
        }
        while (!q.empty()) {
            ListNode *tmp = q.top();
            q.pop();
            pre->next = tmp; 
            pre = tmp;
            tmp = tmp->next;
            if (tmp != nullptr) q.push(tmp);
        }

        return dummynode->next;
    }   
};
最后修改:2021 年 04 月 03 日 10 : 18 PM