双指针是一种应用很广泛且基础的编程技巧，双指针中的“指针”是指索引、游标。
一、双指针思想
双指针是指在遍历对象的过程中，不是普通的使用单个指针进行访问，而是使用两个指针进行遍历，从而达到相应的目的。
最常见的双指针算法有两种：
- 在同一个序列中，用两个指针维护两个位置，或两个位置包含的区间；
- 在两个序列里边，两个指针指向不同的序列，来维护某种次序。
二、常见算法模型
按照指针的移动方向，双指针分为同向双指针、异向双指针。
同向双指针，也称快慢指针（两个指针一快一慢）；异向双指针，分为对撞指针（从两边向中间移动）、背向指针（从中间向两边移动）。
2.1 快慢指针
两个指针，初始在同一位置，然后向相同方向移动，一个移动速度快，一个移动速度慢。
适用场景：查找链表中间节点、链表是否包含环、原地修改数组。
示例：LeetCode 876.【链表的中间结点】
给你单链表的头结点 head ，请你找出并返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。如下图所示，链表有 5 个节点，返回第 3 个节点；链表有 6 个节点，返回第 4 个节点。
我们可以通过遍历 2 次链表来找到中间节点，第 1 次遍历获取链表长度 len，第 2 次遍历到 len/2 的位置。但是，使用快慢指针只需要遍历一次就可以解决，明显运行效率可以得到提升。
/**
* 获取单链表中间节点
*
* @param head 单链表头节点
* @return 中间节点
*/
public ListNode middleNode(ListNode head) {
ListNode fast = head;
ListNode slow = head;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
}
return slow;
}
示例：LeetCode 26.【删除有序数组中的重复项】
给你一个非严格递增排列的数组 nums ，请你原地删除重复出现的元素，使每个元素只出现一次 ，返回删除后数组的新长度。元素的相对顺序应该保持 一致 。然后返回 nums 中唯一元素的个数。
考虑 nums 的唯一元素的数量为 k ，你需要做以下事情确保你的题解可以被通过：
- 更改数组
nums，使nums的前k个元素包含唯一元素，并按照它们最初在nums中出现的顺序排列。nums的其余元素与nums的大小不重要。 - 返回
k。
思路：如果不是原地修改的话，可以用一个新数组保存去重之后的元素，返回新数组长度即可。但是原地修改，只能在原始数组上操作，所以，需要考虑使用快慢指针。
让慢指针 slow 走在后面，快指针 fast 走在前面，fast找到一个不重复的元素就赋值给 slow 并让 slow 前进一步。这样，就保证了 nums[0..slow] 都是不重复的元素，当 fast 指针遍历完整个数组 nums 后，nums[0..slow] 就是整个数组去重之后的结果。
/**
* 原地删除数组重复元素
*
* @param nums 原始数组
* @return 不重复元素的数量
*/
public int removeDuplicates(int[] nums) {
int fast = 1;
int slow = 0;
int len = nums.length;
while (fast < len) {
// 出现不重复元素
if (nums[fast] != nums[slow]) {
slow++;
// nums[0...slow] 保存不重复元素
nums[slow] = nums[fast];
}
fast++;
}
return slow + 1;
}
示例：LeetCode 27.【移除元素】
给你一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素，并返回移除后数组的新长度。
不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并原地修改输入数组。元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
思路：原地修改数组考虑使用快慢指针。
让慢指针 slow 走在后面，快指针 fast 走在前面，fast遇到值为 val 的元素直接跳过，否则就赋值给 slow 并让 slow 前进一步。这样，就保证了 nums[0..slow] 都是不为val的元素，当 fast 指针遍历完整个数组 nums 后，nums[0..slow] 就是需要的结果。
/**
* 移除值为 val 的元素
*
* @param nums 原始数组
* @param val 移除的元素值
* @return 移除值为 val 的元素后，数组的长度
*/
public int removeElement(int[] nums, int val) {
int fast = 0;
int slow = 0;
int len = nums.length;
while (fast < len) {
if (nums[fast] != val) {
nums[slow] = nums[fast];
slow++;
}
fast++;
}
return slow;
}
2.2 对撞指针