双指针链表题学习笔记

学习网址：https://labuladong.online/zh/algo/essential-technique/linked-list-skills-summary/

链表题特点

单向链表无法从尾部回溯，很多题不能像数组那样直接倒着处理。

链表题的核心通常不是操作节点值，而是调整节点之间的指针关系。

因为不容易直接拿到前驱节点，所以常见做法是：

• 额外维护前驱指针
• 用双指针制造位置关系
• 用 dummy 节点补出头结点前面的“虚拟位置”

常见题型可以分为两类：

• 重组类
  ：合并、分解、拼接
• 定位类
  ：倒数第 k 个、中点、环、交点

删除类题目通常可以转化为：先找到待删除节点的前驱，再改指针。

虚拟头（dummy）节点技巧

当题目需要创建新链表时，优先考虑 dummy 节点。

当头结点可能被删除、替换或重新连接时，也优先考虑 dummy 节点。

dummy 的价值不在于优化复杂度，而在于：

• 统一头节点和普通节点的处理逻辑
• 减少边界判断
• 避免大量特判空指针

常见使用场景：

• 合并两个有序链表
• 分解 / 拼接链表
• 删除倒数第 N 个节点
• 任何“可能改动原头结点”的题

题目讲解笔记

合并两个有序链表：拉拉链

核心思路

用两个指针分别遍历两条有序链表，把较小节点依次接到dummy节点后面。

注意点

• 每轮只接较小的那个节点。
• 任一链表走完后，另一条剩余部分直接接上即可。
• 这题重点是“改指针”，不是“新建所有节点”。
• 这是很多链表重组题的基础模板。

单链表的分解：注意断开原链表链接

核心思路

遍历原链表，把节点按条件分别接到两条新链表，最后再拼起来。

注意点

• 如果复用原链表节点，就要注意断开原来的next。否则旧链接可能残留，导致结果错误，甚至形成环。

这类题本质上是“拆分 + 重连”。

合并 k 个有序链表：堆排序找最小头节点

核心思路

每次从 k 条链表当前头结点里选出最小的接到结果链表后，再把该节点的下一个节点放回候选集合。

注意点

• 与合并两个有序链表的思路相同，只是找最小节点的算法不同
• 时间复杂度是 O(Nlogk)：每次维护堆的浮渣度是O(logk)，每个节点都要加入堆因此是O(Nlogk)

单链表的倒数第 k 个节点：双指针固定间距

核心思路

先让快指针走 k 步，再让快慢指针一起走；当快指针走到尾部时，慢指针正好指向倒数第 k 个节点。

注意点

• 关键不只是双指针，而是先制造出固定间距。
• 这是“单次遍历定位”的典型技巧。

单链表的中点：快慢指针

核心思路

慢指针一次走一步，快指针一次走两步；快指针到尾时，慢指针就在中点。

注意点

• 这题本质上也是一种“双指针位置关系”。
• 循环条件不同，返回的中点也可能不同。
• 常见写法在偶数长度链表中会返回靠后的中点

• 需要对“返回前中点还是后中点”保持敏感。

判断链表是否成环：快慢指针追及

核心思路

慢指针一次走一步，快指针一次走两步：

如果无环，快指针最终会遇到null

如果有环，快慢指针最终会相遇，原因如下：

• 快慢指针都会进入环内
• 快指针与慢指针在环内的相对速度是1，因此快指针肯定会与慢指针相遇而不会“错过”

找环起点：相遇点和起始点到环起点的距离都是k-m

注意点

• 不仅要会判断有无环，还要会找环起点。
• 快慢指针第一次相遇后，让一个指针回到头结点，两指针改为同速前进，再次相遇的位置就是环入口

两个链表是否相交：核心是尾部对齐

核心思路

核心如何让在于两个链表的指针同时到达相交点，即尾部要对齐。

方法一：先算长度差，让长链表的头指针先走几步

方法二：A+B和B+A长度相同，从而实现尾部对齐

注意点

• 难点在于两条链表长度可能不同，起点天然不对齐。
• 如果相交，会在交点相遇；如果不相交，会一起走到