我要招人

去企业版

首页 > 试题广场 >

合并k个已排序的链表

[编程题]合并k个已排序的链表

热度指数：179593 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

合并 k 个升序的链表并将结果作为一个升序的链表返回其头节点。

数据范围：节点总数 $0 \le n \le 5000$ ，每个节点的val满足 $|val| <= 1000$

要求：时间复杂度 $O(nlogn)$

示例1

输入

[{1,2,3},{4,5,6,7}]

输出

{1,2,3,4,5,6,7}

示例2

输入

[{1,2},{1,4,5},{6}]

输出

{1,1,2,4,5,6}

说明：本题目包含复杂数据结构ListNode，点此查看相关信息

算法知识视频讲解

牛客题解官

发表于 2022-04-22 11:23:18

精华题解题目的主要信息：给定k个排好序的升序链表将这k个链表合并成一个大的升序链表，并返回这个升序链表的头举一反三：学习完本题的思路你可以解决如下题目： BM4.合并有序链表 BM6.判断链表中是否有环 BM7.链表中环的入口节点 BM8.链表中倒数最后k个节点 BM9.删除链表的倒数第n个节点展开全文

Maokt

发表于 2021-07-12 16:41:35

精华题解算法思想一：辅助数组解题思路主要采用将列表中的链表结点值遍历存储到辅助数组中，再对数组进行排序，根据排序后的数组元素一次构建新链表 1、遍历列表，分别将每一个链表的元素值存储到数组tmp中 2、对tmp进行排序 3、依次遍历数组元素创新新链表代码展示：展开全文

未来0116

发表于 2021-07-15 10:41:33

精华题解一.题目描述NC51合并k个已排序的链表题目链接:https://www.nowcoder.com/practice/65cfde9e5b9b4cf2b6bafa5f3ef33fa6?tpId=188&&tqId=38611&rp=1&ru=/activity/oj& 展开全文

LaN666

发表于 2021-03-07 19:54:53

三种解法分治顺序合并优先队列首先做这道题，得先会一道基础的题目，没做过的可以先去做合并两个已排序的链表分治（归并）先分而治之，分到不能再分则合并(归并) 图解： import java.util.*; public class Solution { public ListN 展开全文

Vetrs

发表于 2020-08-30 20:34:20

//递归方法：//分治思想，逐一攻破 class Solution { public: ListNode *mergeKLists(vector<ListNode *> &lists) { if(lists.size() == 0) 展开全文

于1111

发表于 2020-09-13 21:18:23

merge的返回值，当left>=right,则说明全都有序，此时只需要返回list.get(low)即可。 /** * 合并k个已排序的链表并将其作为一个已排序的链表返回。 * 分析并描述其复杂度。---熟悉mergeSort,返回值不同！！当low>=hi 展开全文

tanglin3438

发表于 2022-04-03 07:44:21

# class ListNode: # def __init__(self, x): # self.val = x # self.next = None # # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # # @para 展开全文

Carmen-Xiao

发表于 2021-11-22 20:22:20

分而治之！本题能过很好的理解分治和递归。做本题之前，可以做一下https://leetcode-cn.com/problems/merge-two-sorted-lists/这个题目！我们如果能够做到合并两个有序的链表，剩下的就是分治算法的思维了。思路分析：展开全文

麻豆出品

发表于 2020-09-06 16:23:16

首先吐槽一下，有些老铁采用了这种投机取巧的方法：直接遍历列表，取出每个链表里面的值然后进行数组排序，最后再依次插入到一个新链表中。喂，你要这么写，那面试官只能面带微笑的告诉你：“写的不错，今天的面试就先到这里吧。”很明显这种解法走偏了，自己刷题可以试，面试可别这么整。这种题其实就是两个有序链表合并展开全文