链表

一句话：链表题几乎都是指针操作的模式化组合，真正的武器只有两件——虚拟头节点（dummy）消灭”头节点要不要特判”的分支，和快慢指针。认出该用哪件武器，代码本身反而是最不费脑子的部分。

虚拟头节点：消灭头节点特判

19-删除倒数第N个结点、24-两两交换、25-K个一组翻转、92-反转链表II 都有一个共同的坑：如果操作可能发生在头节点上，头节点就需要单独判断——删的恰好是第一个，交换的恰好是前两个，反转的区间恰好从头开始。

解法统一：造一个 dummy.next = head，所有操作都基于 dummy 出发，返回时用 dummy.next。头节点从此和其他节点一视同仁，不再需要任何特判分支。这不是奇技淫巧，是消除边界条件的正规做法——只要题目涉及”可能修改头节点”，先反射性地加一个 dummy。

反转：三指针滚动

206-反转链表 是模板：prev/cur/next 三个指针滚动，每步先存 next 再断链再前移，写反了顺序就会丢失后续链表。92-反转链表II（区间反转）和 25-K个一组翻转 都是这个模板的组合应用——先定位区间的前驱和后继，反转区间内部，再把前驱后继接回去。难点从来不是反转本身，是反转前后怎么把断开的两头正确接回去，建议先画图标出反转前后 4 个关键节点（区间前驱、区间头、区间尾、区间后继）。

快慢指针：一个指针的信息差

快慢指针（一个走一步、一个走两步）能回答三类问题，本质都是利用”两者的步数差”提取信息：

• 找中点（876-链表的中间结点）：快指针到终点时，慢指针恰好在中点。
• 判环 + 找环的入口（141/142-环形链表）：快慢指针相遇即有环；相遇后让其中一个指针回到头节点，两者以相同速度前进，再次相遇的节点就是环的入口——这是一个可以直接背下来但也值得推一遍数学证明的结论（相遇点到环入口的距离 = 头节点到环入口的距离）。
• 删除倒数第N个（19）：快指针先走 N 步，之后两指针同速前进，快指针到终点时慢指针恰好在倒数第 N 个前一个位置。

易混：深拷贝 vs 找交点

138-复制带随机指针的链表 和 160-相交链表 都在处理”节点关系”，容易被当成同一类，但解决的是完全不同的问题：138 是要复制出一份结构相同但节点全新的链表（哈希表映射原节点→新节点，或”原地interleave”技巧省空间）；160 是要在两条已存在的链表里找到同一个物理节点（把长度差消化掉——两个指针各走一遍对方的链表，路程相同时必然同时到达交点或同时为 null）。前者关心”复制”，后者关心”重合”，思路不能互相套用。