不能直接套用数组快排的partition逻辑，因为单向链表无法随机访问和反向遍历，强行模拟会导致O(n²)时间复杂度及边界错误；正确做法是用三路划分+哑节点仅遍历一次完成归类，并严格处理断链与拼接。
为什么不能直接套用数组快排的 partition 逻辑
数组快排依赖随机访问（arr[i]），而单向链表只能从头逐个遍历。若强行模拟“取中位数”或“双向扫描交换”，会因无法反向移动指针导致时间退化为 O(n²)，且边界判断极易出错。
关键约束：只能用 next 指针前进，没有 prev；每次比较和移动都需额外遍历，必须避免重复扫描。
- 错误做法：在 partition 中反复从 head 往后找第 k 个节点——单次 partition 就变成 O(n²)
- 正确思路：用「三路划分」代替传统双路，只做一次遍历完成小于/等于/大于基准的归类
- 基准选法建议固定用头节点值（
head->val），避免为找中位数额外遍历
如何用三个哑节点完成一趟 partition（无内存分配）
不 new 节点、不复制数据，仅重连指针。用三个哑节点分别收集小于、等于、大于基准的节点：
ListNode dummy_lt(0), dummy_eq(0), dummy_gt(0); ListNode *lt = &dummy_lt, *eq = &dummy_eq, *gt = &dummy_gt;
遍历原链表时，把每个节点摘下后挂到对应哑节点尾部，最后拼接：lt->next = dummy_eq.next; eq->next = dummy_gt.next;。
立即学习“C++免费学习笔记（深入）”；
- 注意：必须保存
next指针再移动当前节点，否则链断裂：ListNode* next = cur->next; cur->next = nullptr; - 拼接前要确保各段末尾为
nullptr，否则可能成环（尤其dummy_gt段为空时） - 返回时跳过哑节点：
return dummy_lt.next ? dummy_lt.next : (dummy_eq.next ? dummy_eq.next : dummy_gt.next);
递归边界与断链处理的关键细节
单向链表无法像数组那样靠索引切分，必须显式断开子链首尾。常见崩溃点是忘记置空最后一个节点的 next，导致子链仍连着后续无关节点。
- 递归前必须分离三段：获取
lt_tail、eq_tail、gt_tail，并设lt_tail->next = eq_tail->next = gt_tail->next = nullptr; - 空链表或单节点直接返回，但要注意：单节点时
eq段有值，lt和gt均为空，此时不能对空段递归 - 递归调用应只传非空段的头节点：
sortList(dummy_lt.next)，而非&dummy_lt
面试时最容易被追问的性能与稳定性问题
这个实现平均 O(n log n)，但最坏仍是 O(n²)（已排序链表选头为基准）。稳定？否——相同值节点的相对顺序在 eq 段内保持，但 lt 和 gt 段来自不同原始位置，整体不稳定。
- 优化方向：随机选基准需先遍历计数再随机跳转，代价高；改用「中位数的中位数」过于复杂，面试中提一句即可
- 空间复杂度是 O(log n)（递归栈），不是 O(1)；若要求 O(1) 空间，得改写为迭代+模拟栈，极难且非常规
- 真正容易翻车的是：没处理空指针解引用（如
head->next前未判head是否为空）、拼接后忘记返回新头节点
链表快排的核心不在“快”，而在“如何用有限指针操作规避随机访问缺陷”。每一步断链、挂载、拼接，都得盯着 next 指针的归属和生命周期。
