我要招人

去企业版

首页 > 试题广场 >

单链表的排序

[编程题]单链表的排序

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

给定一个节点数为n的无序单链表，对其按升序排序。

数据范围： $0 < n \le 100000$ ，保证节点权值在 $[-10^9,10^9]$ 之内。

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

示例1

输入

[1,3,2,4,5]

输出

{1,2,3,4,5}

示例2

输入

[-1,0,-2]

输出

{-2,-1,0}

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

算法知识视频讲解

Maokt

发表于 2021-07-16 14:24:31

精华题解算法思想一：辅助数组解题思路：主要通过辅助数组实现链表的排序 1、遍历链表并将链表结点存储到数组 tmp 中 2、通过对 tmp 进行排序，实现链表结点的排序 3、构建新链表结点 result，遍历数组 tmp ，拼接新的返回链表图解：展开全文

牛客题解官

发表于 2022-04-22 11:33:05

精华题解题目的主要信息：给定一个无序链表，要将其排序为升序链表举一反三：学习完本题的思路你可以解决如下题目： BM5.合并k个已排序的链表 BM20.数组中的逆序对方法一：归并排序（推荐使用）知识点1：分治分治即“分而治之”，“分”指的是将一个大而复杂的问题划分成多个性质相同但是规模更小的子展开全文

2019113913

发表于 2021-07-15 21:44:16

精华题解题意思路：给定一个无序单链表，实现单链表的排序(按升序排序)。方法一:利用stl和sort排序先新建一个vector，将单链表的元素存储于vector sort排序从小到大将vector变成单链表复杂度分析时间复杂度：O(NlogN)，N链表的长度，遍历链表，排序复杂度NlogN；空间复展开全文

LaN666

发表于 2020-12-06 15:59:48

值排序，不是真正做到链表排序，直接遍历整个链表，用一个数组存储所有的val，然后进行排序，最后将排序完的值赋值给链表 import java.util.*; public class Solution { public ListNode sortInList (ListNode head) { 展开全文

飘过的小牛

发表于 2021-03-15 15:05:55

链表的特点决定了只能从前往后的遍历，我的第一个思路是冒泡排序，但是超时，看了一眼归并排序的写法，真的是妙啊。 1 冒泡（未通过） public ListNode sortInList (ListNode head) { // write code here 展开全文

Kytron

发表于 2021-09-14 17:42:24

快速排序c++写法超99%时间写法 /** * struct ListNode { * int val; * struct ListNode *next; * }; */ class Solution { public: /** * * @pa 展开全文

梦会绽放

发表于 2022-01-31 12:51:58

思路：快速排序。要求时间复杂度为 O(nlogn)，对我们选取的排序算法做出了限制，我们知道时间复杂度为 O(nlogn)的算法有快排、堆排序、归并排序。这里考虑使用快排。复杂度平均时间复杂度O(nlog n),空间发复杂度O(n) 图示代码（JAVA实现） public class 展开全文

hongjunxin

发表于 2020-12-10 23:21:05

解题思路用 vector<ListNode*> 先存储链表中各个节点使用 sort 对 vector 进行排序将 vector 中的 ListNode 按顺序串联起来 /** * struct ListNode { * int val; * struct Li 展开全文

这还不简简单单？

发表于 2021-09-18 19:27:08

/** * struct ListNode { * int val; * struct ListNode *next; * }; */ /** * * @param head ListNode类 the head node * @return ListNode类 * 展开全文

牛客516598323号

发表于 2020-09-13 19:08:28

真的用链表去做很可能会超时。2333。简单搜索了一下，基本上都是改变链表每项内部数据的，而不是把链表重新连接。2333。用例通过率: 100.00% 运行时间: 233ms 占用内存: 11704KB. # # 离经叛道的方法 # @param head ListNode类 the head nod 展开全文