双指针（Two Pointers）
通过在数据结构上使用两个指针协同移动，将嵌套循环优化为单次线性扫描的算法技巧。
定义
双指针是一种算法设计技巧，通过在数据结构（通常是数组或链表）上使用两个指针协同移动，将原本需要嵌套循环的操作优化为单次线性扫描，时间复杂度从 O(N²) 降低到 O(N)。
核心思想
| 特性 | 说明 |
|---|---|
| 本质 | 用两个指针的协同移动，替代嵌套循环 |
| 时间优化 | 从 O(N²) 降低到 O(N) |
| 空间复杂度 | 通常为 O(1)，原地操作 |
| 适用结构 | 数组、链表、字符串等线性结构 |
常见模式
1. 对向指针（左右夹逼）
两个指针分别从两端向中间移动，适用于有序数组的查找问题。
经典应用：
- 两数之和（有序数组）
- 反转数组
- 验证回文串
示意：
初始： [1, 2, 3, 4, 5, 6]
↑ ↑
left right
最终： [1, 2, 3, 4, 5, 6]
↑
left/right 相遇
2. 快慢指针（Fast & Slow）
快指针移动速度快于慢指针，用于定位特定位置或检测环。
经典应用（链表场景）：
- 寻找倒数第k个节点（快指针先走k步）
- 寻找链表中间节点（快指针2步/次，慢指针1步/次）
- 检测链表是否有环（Floyd 判圈算法）
- 找到环的起点
示意：
寻找中点：
慢指针：1步/次
快指针：2步/次
初始： 1 → 2 → 3 → 4 → 5 → null
↑ ↑
slow fast
最终： 1 → 2 → 3 → 4 → 5 → null
↑ ↑
slow fast(null)
3. 双指针拼接（逻辑拼接）
两个指针分别遍历不同结构，通过逻辑拼接实现同步。
经典应用（链表场景）：
- 判断两个链表是否相交（A+B = B+A 逻辑）
- 合并两个有序链表（拉拉链模式）
4. 滑动窗口（Sliding Window）
双指针形成窗口，根据条件动态调整窗口大小。
经典应用：
- 最小覆盖子串
- 无重复字符的最长子串
- 和≥target的最短子数组
5. 中心扩散（从中心向两端）
左右指针从中心位置向两端扩展，常用于回文串问题。
经典应用：
- 回文串判断
- 最长回文子串（奇数/偶数长度）
示意：
最长回文子串（中心为i，奇数长度）：
初始： a b a
↑
l/r
扩展： a b a
↑ ↑
l r
最长回文子串（中心为i,i+1，偶数长度）：
初始： a b b a
↑ ↑
l r
扩展： a b b a
↑ ↑
l r
在链表中的应用
本文总结的7大技巧均基于双指针：
| 技巧 | 双指针模式 | 说明 |
|---|---|---|
| 合并两个有序链表 | 双指针拼接（拉拉链） | p1、p2分别遍历两个链表 |
| 链表分解 | 双指针拼接 | p1遍历原链表，p2、p3构建两个子链表 |
| 合并k个有序链表 | 优先级队列辅助 | 双指针用于合并两个链表的基础操作 |
| 倒数第k个节点 | 快慢指针（领先k步） | 快指针先走k步，然后同步 |
| 寻找中点 | 快慢指针（2:1速度） | 快指针2步/次，慢指针1步/次 |
| 判断环/找环起点 | 快慢指针（Floyd算法） | 相遇即环，重置后同步找起点 |
| 判断交点 | 双指针拼接（A+B逻辑） | p1、p2分别遍历A、B，末尾互换 |
在数组中的应用
快慢指针（同向）
| 技巧 | 双指针模式 | 说明 |
|---|---|---|
| 删除有序数组重复项 (#26) | 快慢指针 | fast探路，不同则赋值给slow |
| 移除元素 (#27) | 快慢指针 | fast跳过val，有效元素赋给slow |
| 移动零 (#283) | 快慢指针 | 复用#27移除0，后半部分置0 |
| 滑动窗口 | 快慢指针（窗口） | right扩大窗口，left缩小窗口 |
左右指针（对向/中心扩散）
| 技巧 | 双指针模式 | 说明 |
|---|---|---|
| 二分查找 | 对向指针 | left=0, right=n-1，根据mid调整 |
| 两数之和-有序数组 (#167) | 对向指针 | 根据sum与target比较移动指针 |
| 反转数组/字符串 (#344) | 对向指针 | 交换left和right，向中间靠拢 |
| 回文串判断 | 对向指针 | 比较两端字符，向中间检查 |
| 最长回文子串 (#5) | 中心扩散 | 从中心向两端扩展，分奇数/偶数长度 |
| 归并排序（merge） | 双指针拼接 | 两个有序数组的合并 |
| 快速排序（partition） | 双指针分区 | 将数组分为小于/大于等于pivot两部分 |
| 颜色分类（荷兰国旗） | 三指针 | 一次遍历将数组分为三部分 |
与类似概念对比
| 维度 | 双指针 | 滑动窗口 | 分治算法 |
|---|---|---|---|
| 本质 | 两个指针协同 | 双指针的特殊形式 | 递归分解问题 |
| 指针移动 | 根据条件灵活移动 | 根据窗口条件调整 | 不直接使用指针 |
| 典型应用 | 合并、查找、环检测 | 子串/子数组问题 | 归并排序、快速排序 |
| 时间复杂度 | O(N) | O(N) | O(N log N) |
注意事项
- 边界条件：注意指针的移动条件和终止条件，避免空指针异常
- 指针速度：快慢指针的速度比需要根据问题确定（通常是2:1或k:0）
- 虚拟节点：在链表操作中，配合虚拟头结点使用可以简化边界处理
- 逻辑拼接：理解"逻辑拼接"的本质（如A+B），避免试图真的修改链表结构
经典算法
- 数组双指针技巧总结：快慢指针（原地修改、滑动窗口）+ 左右指针（对向、中心扩散）
- 链表技巧总结：7大双指针应用场景
- 归并排序：merge操作中的双指针技巧
- 快速排序：partition操作中的双指针分区