title: Leetcode 23.合并K个排序链表
hidden: true
tags:

• C++
• Leetcode
• 链表
• 优先队列
  categories: Leetcode
  mathjax: false
  date: 2019-05-04 20:11:49

题目描述

合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。

示例:

输入:
[
  1->4->5,
  1->3->4,
  2->6
]
输出: 1->1->2->3->4->4->5->6

题目分析

同 Leetcode 21.合并两个有序链表, 将所有节点放入优先队列后建新表.

源码

struct comp{ // 自定义排序函数
    bool operator()(ListNode* &a, ListNode* &b) {
        return a->val > b->val;
    }
};

class Solution {
public:
    priority_queue<ListNode*, vector<ListNode*>, comp> q; // 用优先队列储存节点

    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if(lists.size() == 0) return NULL; // 如果数组为空则返回NULL
        ListNode* it;
        for(int i=0; i<lists.size(); ++i) { // 遍历所有表并将每个表中所有节点存入优先队列
            it = lists[i];
            while(it != NULL) {
                q.push(it);
                it = it->next;
            }
        }
        if(q.size() == 0) return NULL; // 如果数组中只有空节点则返回NULL
        ListNode* res = q.top();
        q.pop();
        it = res;
        while(q.size() != 0) {
            it->next = q.top();
            it = it->next;
            q.pop();
        }
        it->next = NULL; // ***将最后一个节点的next设为NULL***
        return res;
    }
};