# 双指针问题

这类题型的涉及面非常广，从原地遍历到二分查询都有着该问题的缩影。

但是这里，我将双指针的类型分为两类，首尾指针和快慢指针。可以通过这两类问题的思路来举一反三，通解这一类题型。

# 快慢指针

这一题型在链表问题中十分常用。

例如经典的判断链表是否存在环的问题：[141] 环形链表与 [142] 环形链表 II，实际上就是通过有速度差的快慢指针是否相遇来解决的。

再例如如果要删除链表中的一个节点，那么必然需要两个指针，一个指向被删的前一个节点，一个指向后一个节点。这实际上也是快慢指针的一个用法。

首尾指针的应用范围就更广了，例如最经典的二分查找、归并排序算法，其中都是依靠着对每一个部分进行首尾指针相关的操作，来缩小解题范围，最终逼近确定值的过程。

首尾指针的题型有很多，大体可以分为两类，一类是同向双指针问题，一类是反向双指针问题。

同向双指针问题即为滑动窗口问题，指针初始化在窗口的首尾两侧。本质上就是判断一个区间内的元素是否满足某种条件，如果满足则缩小左边界，如果不满足则扩大右边界。我们会单开一个专题来讲解这一类问题。

反向双指针问题其实更符合首尾指针的定义，即指针初始化在数组的两端，然后向中间移动。这类问题一般是求最值问题，例如求最长回文子串、求最小覆盖子串等。