23. 合并 K 个升序链表

题目描述

给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。

解题思路

这个题目显然是可以用归并排序（区间内单调）的方法——最核心的地方就是合并两个有序链表（力扣第21）

同时也可以用优先级队列的方法，不过要修改比较方法（仿函数）。在优先级队列的方法中，有一个很重要的点，就是把所以节点的后续节点（next）制空，避免出现节点指向出现问题。

代码

归并排序

/**
 * 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:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if(lists.size()==0) return nullptr;
        return merge(lists,0,lists.size()-1);
    }
    ListNode* merge(vector<ListNode*>& lists,int left,int right)
    {
        if(left==right) return lists[left];

        int mid=(left+right)>>1;
        ListNode* l=merge(lists,left,mid);
        ListNode* r=merge(lists,mid+1,right);

        ListNode* phead=new ListNode;
        ListNode* cur=phead;
        //合并两个有序链表
        while(l&&r)
        {
            if(l->val<r->val) cur->next=l,l=l->next;
            else cur->next=r,r=r->next;

            cur=cur->next;
        }
        if(l) cur->next=l;
        else cur->next=r;

        return phead->next;
    }
};

优先级队列

/**
 * 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 {
    struct cmp
    {
        bool operator()(ListNode* a,ListNode* b)
        {
            if(a->val<b->val) return false;
            return true;
        }
    };
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        priority_queue<ListNode*,vector<ListNode*>,cmp> pq;
        for(auto cur:lists)
        {
            while(cur)
            {
                pq.push(cur);
                cur=cur->next;
            }
        }
        ListNode* phead=new ListNode;
        ListNode* cur=phead;
        while(pq.size()!=0)
        {
            //重点，最关键
            pq.top()->next=nullptr;

            cur->next=pq.top();
            cur=cur->next;
            pq.pop();
        }
        return phead->next;
    }
};