如何为singly linked list实现quick sort？（改next pointer而非交换节点值）

这个实现完全满足“仅修改节点next指针、不交换节点存储值”的要求，不需要依赖双向遍历、随机访问这些单链表不具备的结构特性。

原生快排无法直接用在单链表的核心原因 #

传统基于数组的快排依赖两个前提：一是可以O(1)随机访问任意位置的节点，二是可以从段的两端双向遍历做双指针交换。单链表只有单向next指针，没法反向找前驱、没法快速定位任意位置节点，如果硬套数组快排的逻辑，不仅实现复杂度高，还会因为频繁遍历找尾把时间效率拉得很低。

核心改造思路 #

完全抛弃双向交换的分区逻辑，改用单方向遍历就能完成的尾插式分区，全程只需要顺着next指针走一遍，刚好适配单链表的访问特性。所有调整只涉及next指针的修改，不触碰节点存储的实际值。

具体实现步骤 #

1. 分区操作的指针流转逻辑 #

这部分是整个实现的核心，每一步的指针操作都可以直接落地：

• 函数入参传入两个边界：一个是待排序段的前驱哑节点（它的next指向待排序段的第一个节点），另一个是待排序段的结束标记节点（遇到这个节点就停止遍历，不把它纳入本次排序范围）。
• 首先顺着待排序段遍历到最后一个节点，选它当枢轴，然后把这个枢轴节点从链表中临时摘出来：找到它的前驱节点，把前驱的next直接指向枢轴的下一个节点，让枢轴暂时脱离当前的遍历路径。
• 初始化两个临时的哑节点less_head和greater_eq_head，分别用来存所有值小于枢轴、大于等于枢轴的节点，同时配两个对应的尾指针less_tail、greater_eq_tail，初始时两个尾指针都指向对应的哑节点。
• 顺着剩下的待排序段做一次单方向遍历，逐个处理每个节点：
  • 把当前节点从原链表链路上临时摘下来（也就是让它的前驱的next直接指向当前节点的下一个节点），然后把当前节点的next置空
  • 如果当前节点值小于枢轴，就把它挂到less_tail的后面，再把less_tail后移到这个新挂的节点上
  • 如果当前节点值大于等于枢轴，就同理挂到greater_eq_tail后面，移动对应的尾指针
• 所有节点遍历完成后，把之前摘出来的枢轴拼到两个子链表的中间：
  • 让less_tail.next = pivot
  • 让pivot.next = greater_eq_head.next
  • 让greater_eq_tail.next = 传入的结束标记节点，保证分段后的链表结尾和原边界对齐
• 最后把整个拼好的分段结果，接回原来的前驱位置：也就是让最开始的前驱哑节点的next指向less_head.next，整个分区操作就完成了。这时候枢轴已经处在排序完成后应该在的固定位置，左边所有节点值都比它小，右边所有节点值都大于等于它。

2. 递归拆分逻辑 #

• 递归终止条件：如果待排序段的长度小于等于1，也就是前驱哑节点的next直接碰到了结束标记节点，或者待排序段只有一个节点，就直接返回，不需要做任何调整。
• 分区完成后，两个子段的边界不需要额外遍历找，直接靠现有指针就能定位：
  • 左子段（小于枢轴的部分）：前驱就是最开始传入的哑节点，结束标记就是刚放回去的枢轴，直接把这两个边界传给排序函数做递归处理就行
  • 右子段（大于等于枢轴的部分）：前驱就是枢轴本身，结束标记就是最开始传入的结束节点，直接递归处理这个范围
• 整个递归过程没有额外的遍历开销，平均时间复杂度和普通快排一致，为O(nlogn)

避坑细节 #

• 遍历摘节点的时候，一定要先把当前节点的next置空再挂到子链表的尾端，不然很容易出现原链表残留的next指针导致成环、节点丢失的问题
• 不需要强行随机选枢轴，哪怕每次选段尾当枢轴，因为整个过程没有值交换的额外开销，实际运行效率不会比换值的实现差
• 整个实现不需要维护全局的链表头、尾变量，所有分段边界都是通过传入的前驱节点和结束节点定位，递归拼接的时候不会出现位置串错的问题

内容的提问来源于stack exchange，提问作者Abhishek Jaiswal