1. 题目
描述
给定一个节点数为n的无序单链表，对其按升序排序。
数据范围：0<n≤1000000
要求：时间复杂度 O(nlogn)
示例1
输入：
{1,3,2,4,5}
返回值：
{1,2,3,4,5}
示例2
输入：
{-1,0,-2}
返回值：
{-2,-1,0}
2. 解题思路
链表的排序可以采用【归并排序】来完成。假如待排序的链表如下图所示：
归并排序思路图如下：
步骤一：分割链表。
使用快慢指针，找到分割节点。将链表分割为两个链表。采用递归分割，直到不能再分割（不能再分割的条件：节点为空，或只有一个节点）。
步骤二：并（排序）。
将两个（两部分）链表排序。
步骤三：归（回归）。
在此过程将步骤二合并排序的链表返回。
链表节点二分的方法：
-
当节点数量为奇数的情况：
-
当节点数量为偶数的情况：
如果文字描述的不太清楚，你可以参考视频的详细讲解。
-
Python版本：数据结构笔试面试算法-Python语言版_哔哩哔哩_bilibili数据结构笔试面试算法-Python语言版,bilibili课堂,哔哩哔哩课堂,哔哩哔哩,Bilibili,B站,弹幕
https://www.bilibili.com/cheese/play/ep1370400 -
Java版本：哔哩哔哩_bilibili
https://www.bilibili.com/cheese/play/ep1366844 -
Golang版本：哔哩哔哩_bilibili
https://www.bilibili.com/cheese/play/ep1364601
3. 编码实现
核心伪代码如下：
函数 sortInList(链表头节点 head):// 递归终止条件：链表为空或只有一个节点时无需排序（分割）如果 head 为空 或 head.next 为空:返回 head// 步骤1：分割链表// 1.1 使用快慢指针找到中间节点快指针 fast = head.next慢指针 slow = head当 fast 不为空 且 fast.next 不为空:fast = fast.next.next // 快指针每次移动两步slow = slow.next // 慢指针每次移动一步// 1.2 分割为左右两部分右半链表头 new_list = slow.nextslow.next = null // 断开链表，左半部分以 head 开头，右半以 new_list 开头// 1.3 递归处理左右子链表left = sortInList(head) // 递归排序左半部分right = sortInList(new_list) // 递归排序右半部分// 步骤2：合并两个有序链表创建虚拟头节点 tmp_head = ListNode(-1)当前指针 cur = tmp_head当 left 不为空 且 right 不为空:如果 left.val < right.val:cur.next = left // 连接较小节点left = left.next // 左指针后移否则:cur.next = right // 连接较小节点right = right.next // 右指针后移cur = cur.next // 当前指针后移// 处理剩余节点（左或右链表仍有元素）如果 left 不为空:cur.next = left否则:cur.next = right// 步骤3：返回合并后的有序链表头返回 tmp_head.next具体完整代码你可以参考下面视频的详细讲解。
-
Python版本：数据结构笔试面试算法-Python语言版_哔哩哔哩_bilibili数据结构笔试面试算法-Python语言版,bilibili课堂,哔哩哔哩课堂,哔哩哔哩,Bilibili,B站,弹幕
https://www.bilibili.com/cheese/play/ep1370400 -
Java版本：哔哩哔哩_bilibili
https://www.bilibili.com/cheese/play/ep1366844 -
Golang版本：哔哩哔哩_bilibili
https://www.bilibili.com/cheese/play/ep1364601
4.小结
链表的排序用到了归并排序，即分割链表，再合并排序，最后回归。难点是对链表的分割，涉及到多节点指针域的操作，很容易出错。
《数据结构与算法》深度精讲课程正式上线啦！七大核心算法模块全解析：
✅ 链表 ✅ 二叉树 ✅二分查找、排序 ✅ 堆、栈、队列 ✅回溯算法 ✅ 哈希算法 ✅ 动态规划
无论你是备战笔试面试、提升代码效率，还是突破技术瓶颈，这套课程都将为你构建扎实的算法思维底座。🔥立即加入学习打卡，与千名开发者共同进阶！
-
Python编码实现：数据结构笔试面试算法-Python语言版_哔哩哔哩_bilibili数据结构笔试面试算法-Python语言版,bilibili课堂,哔哩哔哩课堂,哔哩哔哩,Bilibili,B站,弹幕
https://www.bilibili.com/cheese/play/ep1509965 -
Java编码实现：哔哩哔哩_bilibili
https://www.bilibili.com/cheese/play/ep1510007 -
Golang编码实现：数据结构笔试面试算法-Go语言版_哔哩哔哩_bilibili数据结构笔试面试算法-Go语言版,bilibili课堂,哔哩哔哩课堂,哔哩哔哩,Bilibili,B站,弹幕
https://www.bilibili.com/cheese/play/ep1509945
对于链表的相关操作，我们总结了一套【可视化+图解】方法，依据此方法来解决链表相关问题，链表操作变得易于理解，写出来的代码可读性高也不容易出错。具体也可以参考视频详细讲解。
今日佳句：合抱之木，生于毫末；九层之台，起于累土；千里之行，始于足下。