链表如何拆分和归并？快慢指针为什么能找到中点？

简化版

链表拆分常用快慢指针找中点：快指针每次走 2 步，慢指针每次走 1 步，快指针到尾时慢指针在中间。拆开后可分别处理两段，再用尾插或 dummy 归并。

详细版

链表没有随机访问，不能像数组一样通过 mid = (l + r) / 2 直接取中点。因此常用快慢指针在线性扫描中定位中点。

典型流程：

slow 每次走一步，fast 每次走两步。
为了拆成两段，通常还要记录 prev，它是 slow 的前驱。
快指针到达末尾后，slow 附近就是后半段开头。
令 prev.next = null，把链表断成两段。
两段处理完成后，用 dummy 和 tail 归并。

这套模式常用于链表归并排序、重排链表、判断回文前的分半操作。时间复杂度通常是 O(n)，空间取决于后续处理方式。

完整版教学

一、链表为什么不能像数组一样直接取中点

数组有下标和连续内存，知道 mid 后可以 O(1) 访问 arr[mid]。链表只有从一个节点到下一个节点的指针，想访问第 500 个节点，必须从头走 500 步。

这导致链表分治不能频繁“按下标取中间”。如果每次为了找中点都用长度再走一遍，也可以，但写法较绕。快慢指针的价值是用一次遍历同时完成定位。

slow 每轮 +1
fast 每轮 +2
fast 到尾时，slow 走了大约一半

这是速度差带来的自然结果，不是经验技巧。

二、快慢指针如何找到中点

以 1 -> 2 -> 3 -> 4 -> 5 -> 6 为例：

初始：slow=1 fast=1
第1轮：slow=2 fast=3
第2轮：slow=3 fast=5
第3轮：slow=4 fast=null

此时 slow 在后半段开头附近。不同循环条件会让中点偏左或偏右，这要根据题目需求选择。例如拆成两段时，经常希望前半段不要为空，并能断开。

常见写法会维护 prev：

let slow = head, fast = head, prev = null;
while (fast && fast.next) {
  prev = slow;
  slow = slow.next;
  fast = fast.next.next;
}
prev.next = null;

prev.next = null 是真正完成拆分的动作。只找到 slow 但不断链，两段仍然连在一起。

三、偶数长度和奇数长度有什么边界差异

链表长度为奇数时，中点比较自然；长度为偶数时，有两个“中间候选”。比如 1 2 3 4，中点可以理解为 2 或 3。

不同初始化和循环条件会影响结果：

写法	偶数长度结果	常见用途
`fast=head`	slow 偏右	后半段从右中点开始
`fast=head.next`	slow 偏左	前半段长度不小于后半段
记录 prev	可断开 slow 前面	链表归并排序

面试时不要只说“快慢指针找中点”，还要能解释你要的是左中点还是右中点。否则在回文链表、重排链表、归并排序里都可能差一个节点。

四、归并为什么适合链表

链表归并不需要移动数组元素，只需要改指针。两个有序链表合并时，每次取较小的头节点接到结果链尾。

const dummy = new ListNode(0);
let tail = dummy;
while (a && b) {
  if (a.val <= b.val) {
    tail.next = a;
    a = a.next;
  } else {
    tail.next = b;
    b = b.next;
  }
  tail = tail.next;
}
tail.next = a || b;

这段代码没有新建大量节点，只是重接已有节点。链表归并排序常用这点，把排序复杂度做到 O(n log n)，同时避免数组快排在链表上随机访问困难的问题。

五、拆分时最容易漏掉的是断链

找到中点后，如果没有 prev.next = null，前半段仍然连着后半段。递归处理时就可能无限递归，因为“前半段”并没有真正变短。

例如：

1 -> 2 -> 3 -> 4
slow = 3
如果不断开，左半段仍是 1->2->3->4

断链后才是：

1 -> 2 -> null
3 -> 4 -> null

这个细节是链表分治能终止的基础。数组分治靠区间边界缩小，链表分治靠指针断开形成真正的子链。

六、复杂度和应用场景

快慢指针找中点是 O(n)，拆分是 O(1)，两个有序链表归并是 O(n)。如果用于归并排序，总时间是 O(n log n)，递归栈空间通常是 O(log n)。

记忆钩子：链表分治的三件事是“快慢找中点、前驱负责断链、dummy 负责归并”。

七、常见误区与追问

误区：找到 slow 就等于拆分完成。 不对，还必须断开前半段和后半段的连接。
误区：偶数长度中点没有区别。 左中点和右中点会影响前后半段长度，进而影响递归终止和题目语义。
误区：链表排序适合快排。 快排依赖随机访问和原地交换，链表上通常不如归并排序自然。
追问：归并时需要新建节点吗？ 通常不需要，只重接原节点；dummy 只是辅助头节点。
追问：递归归并排序空间是 O(1) 吗？ 不是，递归调用栈一般是 O(log n)，自底向上迭代归并才能进一步压栈空间。

八、加强记忆

链表拆分归并要抓住“链表没有下标”这个根因。快慢指针用速度差找中点，prev 用来断开子链，dummy + tail 用来稳定合并。只要能说清偶数中点、断链和归并不新建节点，你对这套模式就不是只会套模板。

简化版

详细版