双指针（two points）通过设置两个指针不断移动来解决问题的，一般主要用来操作数组，链表以及字符串。双指针的种类比较多，有相向双指针，两个指针从两边往中间移。有背向双指针，两个指针从中间往两边移。还有同向双指针，两个指针同时往一个方向移。还有快慢指针，一个指针每次移动的步数多，另一个指针每次移动的步数少。
相向双指针
相向是面对面的意思，相向双指针就是两个指针从两边往中间移动，大家最常见的可能就是二分法查找以及回文串的判断，我们来看下回文串的判断，使用两个指针分别指向字符串的两端，如果他们指向的字符相等就同时往中间移。
private boolean sentencePalindrome(String s) {
int left = 0;// 左指针。
int right = s.length() - 1;// 右指针。
while (left < right) {
if (s.charAt(left++) != s.charAt(right--))
return false;
}
return true;// 都比较完了，说明是回文串，返回true。
}
背向双指针
背向双指针是指两个指针往两边走，和相向双指针相反，这个可以参考下 马拉车算法 ，求最长回文子串。
同向双指针
同向双指针就是两个指针同时往一个方向移，这个在滑动窗口中一般比较常见。同向双指针中两个指针可以指向同一个对象，也可以指向不同的对象，比如合并两个有序数组，可以让两个指针分别指向两个数组。来看这样一道题，给定一个整数数组 arr[] ，将数组中所有的零移动到数组末尾，同时保持非零元素相对的顺序。
Input:arr[] = {3, 5, 0, 0, 4}
Output: 3 5 4 0 0
这题说的是把 0 移动到数组末尾，非 0 元素移到数组的前面，并且还要保证非 0 元素的相对顺序。可以使用两个指针 left 和 right ，其中 right 始终往右移动，当 right 指向的值不为 0 的时候就和 left 指向的值交换，然后两个指针同时往右移一步，如果 right 指向的值为 0 ，left 不动， right 继续往右移，如下图所示。
void pushZerosToEnd(int[] arr) {
int left = 0;// 左指针。
int right = 0;// 右指针。
int length = arr.length;
while (right < length) {
// right 指向的值不为 0 就和 left 指向的值交换。
if (arr[right] != 0) {
int tmp = arr[left];
arr[left] = arr[right];
arr[right] = tmp;
left++;// 挪完之后左指针也往右移。
}
right++;// 右指针始终往右移。
}
}
快慢双指针
快慢双指针一般也是同向的，使用两个指针，一个走的快一个走的慢。比如找出链表的中间节点，如果链表长度是奇数，返回中间节点，如果链表长度是偶数，返回中间的第二个节点。
Input:LinkedList: 1->2->3->4->5
Output: 3 （链表长度是奇数，返回中间节点）
Input:LinkedList: 2->4->6->7->5->1
Output: 7 （链表长度是偶数，返回中间的第二个节点）
使用快慢指针，快指针每次走两步，慢指针每次走一步，直到快指针走到链表的尾节点，或者快指针为空。如果链表长度是奇数，慢指针会走到中间的那个节点，如果链表长度是偶数，慢指针会走到中间的第二个节点。
int getMiddle(Node head) {
Node fast = head, slow = head;
while (fast != null && fast.next != null) {
fast = fast.next.next;// 每次走两步。
slow = slow.next;// 每次走一步。
}
return slow.data;
}
