空间实现单链表排序)
链表排序，这题在剑指 Offer II 077 里算是一道很有代表性的链表操作题。LeetCode 原题叫“Sort List”，要求对单链表排序，时间 O(n log n)、空间 O(1)。第一次看到这个空间限制，很多人会愣一下：数组排序随手用 Arrays.sort，但链表不能随机访问，很多思路得从头想。这篇文章会把这道题的完整思路、实现细节、边界处理和踩坑经验一次说清楚，适合正在刷题的开发者，也适合想系统梳理链表操作的人。
这道题看起来只是“排序”，实际上考的是三件事：能不能想到用归并排序、会不会把递归改成迭代、能不能把链表切断再接回去而不出环。每一个点都不难，但串在一起，就够让人写半天了。我当初第一次写，代码基本是缝缝补补过样例的，直到把底层的分段逻辑理顺，才觉得真正掌握了。
1. 先看清这道题的三个核心难点
1.1 题目到底在问什么
题目给一个单链表的头节点，要求把它按升序排好，返回新的头节点。输入输出都是链表，所以不能开数组存下来排序再重建，至少不能当作最优解。
一个最直接的想法是：把链表遍历一遍，val全塞进数组，排序之后重新构造链表。这样做逻辑很简单，但额外空间是 O(n)，不符合题目的空间要求。题目说“进阶：在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序”，这就把很多方法挡在门外了。
另外要注意，链表节点的定义只有val和next，没有前驱指针，也没有长度属性。很多在数组里看起来自然的操作，在链表上都会变得别扭。
1.2 链表的三个“麻烦点”
链表排序和数组排序的区别，核心在于三个特性：
- 不能随机访问：数组可以花 O(1) 取中间元素，链表快慢指针找中点要 O(n)。
- 没有长度信息：数组有
length，链表只有一个head，你不知道后面还有多少个节点。 - 拼接容易绕成环：合并两个有序链表的时候，如果 tail.next 指向没有及时断开，就可能出现循环引用，导致程序卡死。
这三个麻烦，正是这道题设计出来要考你的地方。你掌握了链表的基本操作——遍历、断链、拼接，这道题就只是一道普通的归并题；如果这些操作不够熟练，就会在边界条件上反复吃亏。
2. 解法选型：为什么最终落在自底向上归并
2.1 常见排序算法在链表上的表现
先过一遍能用和不能用的方案，不是做无用功，是为了真正理解归并排序在这里的不可替代性。
| 算法 | 时间 | 空间 | 在链表上的表现 |
|---|---|---|---|
| 插入排序 | O(n²) | O(1) | 最基础的链表排序写法，没有额外空间，但时间不达标 |
| 快速排序 | O(n log n) 平均 | O(log n) 平均 | 链表中点不好取，partition 需要频繁交换节点，效率不高 |
| 递归归并排序 | O(n log n) | O(log n) | 思想正确，但递归栈会占用额外空间，不满足常数空间 |
| 迭代归并排序 | O(n log n) | O(1) | 满足所有条件，是这道题的理想解法 |
你会注意到，快速排序在链表上不是不能用，而是不好用。数组快排最自然的方式是双指针从两端往中间走，链表没有前驱指针，双指针操作起来非常别扭。即使改成只用一个指针遍历的写法，partition 时找枢纽节点、交换节点也远比数组麻烦。
递归归并排序思想没问题，但题目说的是“常数级空间”，递归栈会存 O(log n) 的开销，严格来说不达标。面试里你说“我用递归归并，空间 O(log n)”，通常能过，但这道题既然明确写了进阶要求，自底向上迭代归并才是更完整的回答。
2.2 自底向上的整体思路
自底向上归并的思想，一句话总结：先把链表拆成每段长度为 1 的有序链表，两两合并，得到长度为 2 的有序段；再把长度为 2 的有序段两两合并，得到长度为 4 的有序段；重复下去，直到整个链表有序。
举个具体例子。链表是4 -> 2 -> 1 -> 3：
- 第一轮，按步长 1 分段：
[4]和[2]合并成2 -> 4，[1]和[3]合并成1 -> 3，现在链表是2 -> 4 -> 1 -> 3。 - 第二轮，按步长 2 分段：
[2 -> 4]和[1 -> 3]合并成1 -> 2 -> 3 -> 4。
这里不需要递归，只用循环控制步长，每轮从头开始遍历链表，切两段、合并一次、把结果接到结果链表的末尾。
这个思路的好处是：空间可以做到 O(1)，只靠指针移动就能完成所有操作；时间还是 O(n log n)，因为每一轮要把所有节点扫描一遍，一共 log n 轮。
3. 一步步把自底向上归并写出来
3.1 先求链表长度，确定需要多少轮
自底向上的第一步是统计链表长度，因为要按长度判断“后面还有没有足够的节点”，这个长度贯穿整个算法。
int length = 0; ListNode node = head; while (node != null) { length++; node = node.next; }没有这一步，你没法知道循环该到什么时候结束。也可以每轮内部单独判断剩余节点数，但先求出总长度会更清晰，代码也更不容易出错。
3.2 分割链表：核心中的核心
分割操作非常容易写错。我的做法是把“从某个节点开始，切出长度为 s 的一段”封装成一个独立方法：
private ListNode cut(ListNode head, int size) { if (head == null) { return null; } ListNode cur = head; while (--size > 0 && cur.next != null) { cur = cur.next; } ListNode next = cur.next; cur.next = null; // 切断 return next; // 返回下一段的头节点 }这个方法的返回值是“切完之后剩下的那个头节点”，而切下来的这一段，被截断后只剩下从原头到cur的部分。调用的时候要注意，size可能比实际剩余的节点多，这时切出来的段可能不足size个节点，没关系，合并的时候照常合并即可。
这个方法是整道题的“发动机”，很多人的问题就出在这一步的返回值设计上。如果返回的是切下来的段头，你就没法知道接下来该从哪里继续遍历了；如果返回的是剩下的头，每次合并前还要额外找段头，显得啰嗦。返回值设计成“剩余链表的头”，配合外部循环里的cur指针，一切都顺了。
3.3 合并两个有序链表的实现
合并两个有序链表是基础操作，但这里有一个细节值得注意：合并前后的链表可能不是一个完整的独立链表，而是从整条链上切下来的一段，所以合并不用创建新节点，只需要重新组织指针。
private ListNode merge(ListNode l1, ListNode l2) { ListNode dummy = new ListNode(0); ListNode tail = dummy; while (l1 != null && l2 != null) { if (l1.val <= l2.val) { tail.next = l1; l1 = l1.next; } else { tail.next = l2; l2 = l2.next; } tail = tail.next; } tail.next = (l1 != null) ? l1 : l2; return dummy.next; }这里的dummy节点有几个作用：一是避免每次合并都要特判“第一个节点到底该接谁”；二是返回合并后的头节点时不用保存两个链表的头引用。这个写法虽然简单，但它是整个自底向上归并的关键支撑。
3.4 主循环：把分段和合并串起来
有了length、cut和merge，剩下的主循环就不复杂了：外层循环控制步长，内层循环依次处理每两个段。
public ListNode sortList(ListNode head) { if (head == null || head.next == null) { return head; } int length = 0; ListNode node = head; while (node != null) { length++; node = node.next; } ListNode dummy = new ListNode(0, head); for (int step = 1; step < length; step <<= 1) { ListNode pre = dummy; ListNode cur = dummy.next; while (cur != null) { ListNode left = cur; ListNode right = cut(left, step); cur = cut(right, step); pre.next = merge(left, right); while (pre.next != null) { pre = pre.next; } } } return dummy.next; }这段代码的关键在while (cur != null)里。cut(left, step)之后返回的是第二段的头，cut(right, step)之后返回的是下一轮的第一段头。这里必须把这个返回值存好，因为紧接着要作为cur开始下一段合并。我写的时候一开始总是弄混这几个返回值，调试了很久才发现是这里的问题。
外层循环控制步长，每轮结束时step要左移一位，相当于长度加倍。循环终止条件是step < length，因为当步长大于等于链表总长度时，说明整个链表已经成了一整段有序链表，不需要再合并了。
3.5 一个更容易读懂的版本
上面的版本是极力压缩代码的写法，但如果你还不熟练，建议写一个变量名更明确的版本。下面这种写法我在调试的时候更愿意用：
public ListNode sortList(ListNode head) { if (head == null || head.next == null) { return head; } int len = 0; for (ListNode cur = head; cur != null; cur = cur.next) { len++; } ListNode dummy = new ListNode(0); dummy.next = head; for (int step = 1; step < len; step *= 2) { ListNode prev = dummy; ListNode cur = dummy.next; while (cur != null) { ListNode firstHead = cur; ListNode secondHead = cut(firstHead, step); cur = cut(secondHead, step); ListNode merged = mergeTwo(firstHead, secondHead); prev.next = merged; while (prev.next != null) { prev = prev.next; } } } return dummy.next; }差别只在变量命名上，逻辑完全一致。刷题的时候没必要追求所有代码都挤在一起，拆开写、变量名直白，反而更容易在面试中边走边说。
4. 刷这道题最容易踩的坑
4.1 场景一：链表的长度不足一步长
如果step = 4，但当前剩余节点只有 2 个，会发生什么？cut(left, 4)只会从头遍历到最后一个节点，然后返回null。也就是说，right是null，cur也是null。这时merge(left, null)直接返回left本身，相当于把剩下的一段原样接上，不会出错。
但你要意识到，这里的left可能已经经过了之前几个 step 的合并，它内部是基本有序的，直接接上是安全的。
4.2 场景二：切断链表的时机不对
网上很多版本的 cut 写法不一样：
// 这种写法有问题吗？ private ListNode cut(ListNode head, int size) { if (head == null) { return null; } ListNode cur = head; while (size > 1 && cur.next != null) { cur = cur.next; size--; } ListNode next = cur.next; cur.next = null; return next; }这个写法实际上是正确的。但如果你改成while (size > 0 && cur != null)，并且让cur = cur.next，在cur.next == null时会多走一步，导致把已经最后一个节点的 next 置成 null，没有危害，但会让代码变得难以分析。我用这个思路，把 cur 遍历的终止条件写反过，然后找了一个小时 bug，后来才意识到是切段的时候多跳了一个。
4.3 场景三：pre 指针移动位置不对
每次合并完一段，pre要移动到合并后链表的末尾，等待接下一段。如果你忘了移动，下一段合并完之后会直接覆盖掉之前的结果，链表最终残缺不全。
这里有一个经验：合并完之后，不要直接pre = merged，因为 merged 的长度不一定刚好是 2 * step，可能比 step 短（如果到了链表末尾）。用while (pre.next != null) pre = pre.next;是更稳的写法。
4.4 常见问题速查表
| 问题现象 | 原因分析 | 处理办法 |
|---|---|---|
| 排序后链表变短 | 合并前没有把整个剩余链表接着合并后的部分 | 检查pre.next = merged是否在每次合并后执行 |
| while 循环死循环 | cut 方法没有切断 next 引用 | 确认 cut 里cur.next = null |
| 结果正确但超时 | 每轮都从 head 开始重新计算长度 | 长度只算一次，用step < len控制轮数 |
| 中间出现空指针 | 右侧链表为空时 merge 的处理不当 | merge 方法里用l1 != null ? l1 : l2 |
| 返回值不对 | 用 dummy.next 判断错误 | 排序整个链表后返回dummy.next |
| 合并内容顺序混乱 | left/right 分配颠倒 | 记住 left 是前面的段，right 是后面的段 |
4.5 要不要先写递归归并版本
我自己刷题时，有意先写了递归版本，再改成迭代版本。这样做有三个好处：
- 递归版本能帮你更直观地理解“划分—合并”这个过程。
- 把递归改成显式步长控制的版本，能让你感受到空间从 O(log n) 变 O(1) 的差异。
- 面试中如果时间紧，先写递归版本保底，至少思路正确。
递归版本：
public ListNode sortList(ListNode head) { if (head == null || head.next == null) { return head; } ListNode slow = head; ListNode fast = head; ListNode prev = null; while (fast != null && fast.next != null) { prev = slow; slow = slow.next; fast = fast.next.next; } prev.next = null; ListNode left = sortList(head); ListNode right = sortList(slow); return merge(left, right); }这个版本用快慢指针找中点，然后把左半段的 next 断开。递归下去，直到只剩一个节点，再回溯合并。它好写，但不好解释复杂度，因为递归栈超过常数范围。所以最后一定要回到迭代版本。
5. 边界场景与复杂度验证
5.1 长度只有 1 或 2 的情况
长度为 1 的链表根本不需要排序，直接返回。
长度为 2 的链表，第一次循环 step = 1，left 是第一个节点，right 是第二个节点，merge 后返回有序的 2 节点链表。此时 step 变成 2，不满足step < 2，退出循环，返回结果。这个过程虽然只有一次合并，但整个框架仍然正确运行。
如果你用递归版本，长度为 2 时还是需要切分成两个单独节点，再合并回来，多一层调用栈。
5.2 全部逆序和全部相同
全部逆序是归并排序的“最佳输入”之一，每一轮依然稳定地 O(n)，所以时间还是 O(n log n)。
全部相同的链表要特别注意稳定性。题目没有要求稳定排序，<=和<都可以，但在合并时如果用<=，可以保证相同 val 的节点保持相对顺序；用<也不影响正确性，因为值相等时交换位置，结果仍然是升序。我建议统一用<=，这样万一题目扩展成稳定排序的要求，代码也能直接用。
5.3 空间复杂度的严谨讨论
迭代归并排序的额外空间主要来自几个局部变量：dummy、pre、cur、left、right、merge 里的 tail。这些都是常数数量级的引用，不随链表长度增长，所以空间是 O(1)。
递归版本虽然思路正确，但递归深度是 log n，意味着调用栈占用 O(log n) 空间。如果编译器不做尾递归优化，这就是真实的空间开销。题目写了“常数级空间”，所以要选择迭代版本。
时间上，每一轮 step 都翻倍，共 log n 轮；每轮遍历 n 个节点。总时间是 O(n log n)。注意，步骤里的找中点、找长度都是每轮重复的，所以这一轮虽然略像数组归并，但常数略高，实际刷题时完全可接受。
5.4 链表长度很大的时候
如果链表的长度接近几十万，迭代归并的代码稳定性优势就体现出来了。递归版本可能因为递归深度导致栈溢出（虽然 log n 通常不大，但在极端条件下有风险），迭代版本则不存在这个问题。
另外，由于我们预先算了一次总长度，step <<= 1不会写成step << 1这种把步长翻倍错误的方式，循环结束条件才有保证。
6. 从这道题延伸出去的链表操作能力
6.1 链表题的四个基本动作
这道题本质上考的，是链表操作的四个基本动作，拆开来看：
- 遍历：走一遍拿到长度，是最基本的。
- 断链：cut 方法里把一个节点 next 置为 null，这个动作非常关键。
- 合并：merge 操作把两个有序链表串成一条。
- 拼接：在 pre 后面接上合并结果，实现整条链的重组。
这四个动作，在后面的很多链表题里都会反复出现。比如 K 个一组翻转链表、合并 K 个升序链表，本质上都是重复使用这些基本能力。
6.2 和数组归并排序的对比
数组归并排序的思路和链表版一模一样，但实现方式差别很大。数组版要开辅助数组，空间 O(n)；链表版可以原地只需要改指针，空间 O(1)。数组版每一步都要拷贝元素，链表版只要重新指向。
这也是为什么面试官愿意在链表题上考归并排序——它逼着你从“值操作”切换到“指针操作”。数组排序你习惯用下标交换值，链表排序必须改变引用，这背后是对数据结构本身的掌握程度。
6.3 一个更深入的问题：为什么快速排序不常用
快速排序在达到平均时间复杂度上同样优秀，但链表的快排实现要比归并复杂不少。问题主要出在 partition 上：你选定一个 pivot 值，把链表拆成“小于”、“等于”、“大于”三段，再把三段拼接。这看起来不难，但实际写起来要注意维护六个指针，而且链表的随机访问特性决定了 pivot 的选择很难优化，最坏情况容易退化到 O(n²)。所以链表排序优先选归并。
6.4 变形：如果链表有环怎么办
链表排序的前提是单链无环。实际面试中，有个变种题会让“判断链表是否有环”，如果这道题和排序题综合在一起，就必须先判断是否有环，再用快慢指针找环入口，然后断开环再排序。
这个过程又复杂了一些。但只要你熟练掌握了基本的链表操作，比如快慢指针找中点和环入口，再结合 cut 和 merge，就能在环断开后复用同样的归并框架。链表题的很多题都是这么结合出来的。
7. 个人经验与最后的建议
7.1 我踩过的三个具体坑
第一，cut返回之后，我没有更新cur，导致下一轮合并还是从原位置开始。这个问题让我印象最深，因为我当时的调试思路一直在看 merge 是否正确，直到用了小数据手动模拟才发现是 cur 没有更新。链表问题里最可怕的就是这种“指针没有往前走”的错误，它不会立刻报错，但在循环里会遇到奇怪的输出。
第二，用for (int step = 1; step <= len; step <<= 1)，把<=写成了<。当链表长度正好是 2 的幂时，最后一轮合并会漏掉。这个问题很隐蔽，因为大多数样例长度都不是 2 的整数幂。
第三，合并两个链表时，tail.next = (l1 != null) ? l1 : l2，我把这个语句漏了。合并的结果会被截断，最后一段丢失。这个问题在单步调试时能一眼看出来，但如果只看最终结果，你会以为是后面的拼接有问题。
7.2 推荐的做题顺序
如果你是第一遍刷这题，我建议按这个顺序来：
- 先会用递归归并排序做出来，也就是快慢指针 + 递归 merge。
- 再重复写一次迭代归并排序，也就是本文的完整版本。
- 尝试自己从零推导一遍主循环，不看任何参考代码。
- 写完之后，故意破坏一个边界条件（比如漏了断链或漏了 pre 移动），看能不能靠测试样例自己找出来。
第四个步骤听起来有点自虐，但非常有效。链表题本来就是一个“找引用错误”的训练，提前感受这些错误，后面遇到真的容易很多。
7.3 面对面试的解释思路
面试场景下，不需要一上来就写代码。可以先说：时间是 O(n log n) 的排序，我选归并排序；因为链表不支持随机访问，快排不适合；为了保证空间 O(1)，我用迭代归并。然后简单画一个步长变化的示意，再开始写。
写的时候分块说，先写cut，再写merge，最后写主循环。这样面试官能看到你的思路，也方便在你卡壳的时候给提示。
7.4 延伸思考
刷完这道题，还可以顺手看看这几类相关题目：
- K 个一组翻转链表，体会链表拼接对循环的控制。
- 排序链表加随机指针的复制问题，感受指针维护复杂度。
- 双向链表的归并排序，思考前驱指针是否简化了断链操作。
从我的实际体验看，链表排序这道题的价值不在“排序”本身，而在它把所有链表基本操作都压到同一道题里。只要把这四件事——遍历、断链、合并、拼接——练到条件反射，后面再去刷其他链表题会顺很多。最后分享一个小技巧：碰到链表题，先在纸上画四个节点，把所有指针变更都标出来，再写代码，基本不会出错。
