首页 > 试题广场 >

链表排序

[编程题]链表排序
  • 热度指数:84166 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解
在O(n log n)的时间内使用常数级空间复杂度对链表进行排序。
示例1

输入

{30,20,40}

输出

{20,30,40}

说明:本题目包含复杂数据结构ListNode,点此查看相关信息
头像 HhhhHhhh_
发表于 2020-06-18 23:35:27
无非就是归并排序运用在链表上(由于链表不能索引访问,故快排桶排并不合适),拆表用快慢指针即可 import java.util.*; /* * public class ListNode { * int val; * ListNode next = null; * } */ p 展开全文
头像 牛客697564601号
发表于 2020-10-13 11:58:32
快排也是可以的,多几个指针保存下哨兵位的左右子链表,需要注意的是处理当左右子链表为空的情况 时间复杂度O(nlogn),空间复杂度其实是O(logn),因为有栈的开销,但是其他解答里都是归并,其实也差不多,只有那个用cut的是满足题意的 ListNode* sort_inner_ 展开全文
头像 华科不平凡
发表于 2020-08-10 11:35:32
花了一晚上都没整明白,细节太重要啦!!! 里面的几个步骤都是难点:1.自底向上思想;2.断链3.归并4.合链 涉及到的指针操作&&边界条件多,一不小心就入坑了。。。 不过归根结底,还是自己太菜啊。。呜呜 // // Created by jt on 2020/8/8. // 循环实现 展开全文
头像 牛客张立-不足胜有余
发表于 2021-06-23 11:51:33
public ListNode sortList(ListNode head) { if( head == null ){ return head; } List<ListNode> list = new 展开全文
头像 流夜
发表于 2021-10-28 18:44:50
import java.util.*; /* * public class ListNode { * int val; * ListNode next = null; * } */ public class Solution { /** * * @ 展开全文
头像 恒成立
发表于 2021-03-27 19:55:42
时间复杂度为: nlog(n)归并排序的时间复杂度是 nlog(n)解题思路:1.找到链表的中间节点2.注意:要保证从head到mid之后,就不能继续排序所以要将mid.next备份为midNext,并将mid.next置为null3.归并排序链表 import java.util.*; /* 展开全文
头像 ZackHuang
发表于 2020-08-14 16:56:39
class Solution { public: ListNode* slow = nullptr, * fast = nullptr, * head = nullptr, * cur=nullptr; ListNode* sortList(ListNode* head) { 展开全文
头像 ywl0211
发表于 2021-10-25 16:57:10
# class ListNode: # def __init__(self, x): # self.val = x # self.next = None # # # @param head ListNode类 # @return ListNode类 # 展开全文
头像 牛客808484225号
发表于 2022-08-08 09:43:05
import java.util.*; /*  * public class ListNode {  *   int val;  *   ListNode next = null;  * }  */ pub 展开全文
头像 怎么不被卷飞
发表于 2021-06-30 11:27:37
//归并排序注意合并时 排序使用两个指针 ,避免两次循环的排序方法 import java.util.*; /* * public class ListNode { * int val; * ListNode next = null; * } */ public class S 展开全文