23. 合并 K 个升序链表

简介: 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;
    }
};
相关文章
|
1天前
23.合并K个升序链表
23.合并K个升序链表
|
6天前
|
存储 算法 数据挖掘
Leetcode二十三题:合并K个升序链表【22/1000 python】
Leetcode二十三题:合并K个升序链表【22/1000 python】
|
8天前
|
存储 人工智能 测试技术
每日练习之排序——链表的合并;完全背包—— 兑换零钱
每日练习之排序——链表的合并;完全背包—— 兑换零钱
13 2
|
19天前
|
索引
【力扣刷题】回文链表、环形链表、合并两个有序链表
【力扣刷题】回文链表、环形链表、合并两个有序链表
18 0
|
24天前
【一刷《剑指Offer》】面试题 17:合并两个排序的链表
【一刷《剑指Offer》】面试题 17:合并两个排序的链表
|
1月前
|
Java C语言
剑指offer(牛客)——合并两个排序的链表
剑指offer(牛客)——合并两个排序的链表
12 1
|
1月前
【移除链表元素】LeetCode第203题讲解
【移除链表元素】LeetCode第203题讲解
|
5天前
|
存储 SQL 算法
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表
|
2天前
|
算法
【经典LeetCode算法题目专栏分类】【第7期】快慢指针与链表
【经典LeetCode算法题目专栏分类】【第7期】快慢指针与链表
|
5天前
|
存储 SQL 算法
LeetCode 题目 86:分隔链表
LeetCode 题目 86:分隔链表