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