链表归并排序实现 O(1) 辅助空间的关键是采用自下而上的迭代归并（bottom-up），而非递归；它通过固定步长逐轮合并有序子链，仅用常数个指针在原链表上截断、拼接，避免递归栈和额外节点分配。

链表归并排序做到 O(1) 辅助空间复杂度，关键不在于“不用递归”，而在于彻底避开递归栈 + 避免额外节点分配 + 仅靠指针重连完成所有操作。这要求放弃自上而下的分治逻辑，改用自下而上的迭代归并——也就是 bottom-up 归并排序。

为什么递归归并做不到 O(1) 空间？

传统递归归并需不断拆分链表（找中点、断链），每层递归都压入调用栈，深度为 O(log n)，自然带来 O(log n) 空间开销。即使只用几个指针变量，栈帧本身无法省略。

• 快慢指针找中点 → 每次递归调用都新增栈帧
• 递归合并 → 合并函数自身也递归，叠加空间消耗
• 即使手动模拟栈，仍属 O(log n) 额外空间

bottom-up 迭代归并：真正 O(1) 的核心机制

它把链表看作 n 个长度为 1 的有序子链，然后按固定步长 step = 1, 2, 4, … 逐轮合并相邻子链。全程只用几个指针（preTail、h1、h2、nextHead、cur）在原链表上滑动、截断、拼接，不 new 节点、不 malloc、不递归。

• step 控制子链长度：第一轮合并所有相邻单节点对；第二轮合并所有相邻两节点组；依此类推
• cut 操作代替断链递归：写一个辅助函数，从某位置起切出前 step 个节点，并返回剩余头节点，不依赖中点查找
• preTail 维护合并段前驱：确保每次 merge 结果能无缝接回主链，避免断链丢失
• nextHead 定位下一段起点：在合并 h1 和 h2 后，立刻知道后续该从哪继续，无需回溯

合并两个有序子链：无额外空间的硬核写法

合并函数本身必须是纯指针操作。使用哑节点（dummy）仅用于简化头结点处理，dummy 是栈上变量，不计入辅助空间；其 next 域指向结果头，合并完直接返回 dummy→next。

• 不分配新节点，只调整已有节点的 next 指针
• 用临时指针 tmp 在 dummy 后逐个挂载 h1/h2 中较小者
• 剩余未尽链表直接链到 tmp→next，无拷贝、无遍历复制
• 全程只使用常数个指针变量（h1、h2、tmp、dummy 等）

实际编码中容易踩的坑

看似逻辑清晰，但链表指针操作容错率极低，稍有不慎就断链或成环。常见疏漏包括：

• cut 后忘记置 h1→next = NULL，导致后续 merge 误读多余节点
• merge 完未将 preTail→next 指向合并结果头，造成段间脱节
• 未正确更新 cur = nextHead，导致内层 while 循环跳过后续段
• step 超过链表长度时未及时 break，引发空指针解引用
• 边界 case（空链、单节点、两节点）未统一覆盖，测试通过但上线崩溃