链表排序

[编程题]链表排序

热度指数：84324 时间限制：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.*; /* 展开全文