双指针常用方法

1.双指针介绍

双指针是解题时一种常见的思路，一般有两种用法。

1）两个指针反方向，分别从数组开头和结尾开始移动，例如对有序数组的搜索。

2）两个指针同方向移动，例如快慢指针，都是从数组开头开始遍历，只是速度不一样。

除了用于数组，也可以用于链表，树，图。

2.反向的双指针

力扣https://leetcode.cn/problems/two-sum-ii-input-array-is-sorted/

因为数组是非递减的，所以可以数组首尾各置一个指针，若值相加大于目标值，则尾指针自减，若值相加小于目标值，则头指针自增，这样就一步步逼近了目标值。

class Solution {
public:vector<int> twoSum(vector<int>& numbers, int target) {int i = 0, j = numbers.size()-1;while(i<j){int t = numbers[i] + numbers[j];if(target==t) return vector<int>({i+1,j+1});else if(target>t){i++;}else{j--;}}return vector<int>();}
};

3.同向的双指针

力扣https://leetcode.cn/problems/linked-list-cycle-ii/这题有两个要点，先是要判断链表中是否有环，接着是找到环的入口。

判断是否有环，可以用快慢指针。

两个指针同时从起点出发，快指针一次两步，慢指针一次一步。

如果链表中有环，则快慢指针一定会相遇，就像在操场上一直跑圈，速度快的人一定会在某一刻比速度慢的人多跑一圈，所以二人相遇了。

若是快慢指针没有相遇，且快指针指向了NULL，那很明显，就是没有环。

确定链表有环后，就是寻找环的入口了。

可以用题目中的示例来简单理解一下。

下图使用快慢指针，从起点[3]出发，慢指针一次一步，快指针一次两步，很快这两个指针会在节点[-4]相遇。

相遇后，将慢指针移回链表起点[3]，快慢指针都一次走一步，两个指针再次相遇的节点[2]，就是环的入口。

 一个简单易懂的解释就是：

慢指针路径：起点--环的入口--快慢指针相遇的节点

快指针路径：起点--环的入口--快慢指针相遇的节点--环的入口--快慢指针相遇的节点

因为快指针路径==慢指针路径*2

所以【快慢指针相遇的节点--环的入口--快慢指针相遇的节点】== 【 起点--环的入口--快慢指针相遇的节点】

同时减去【环的入口--快慢指针相遇的节点】

所以【快慢指针相遇的节点--环的入口】== 【 起点--环的入口】

所以找到环得到入口就是将慢指针移到起点，与快指针都是一次一步，直到相遇，相遇节点就是环的入口。

如果还是没有理解的，可以直接搜索【Floyd 判圈法】找动画视频直观理解一下。

代码：

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:ListNode *detectCycle(ListNode *head) {if(!head) return NULL;ListNode* slow = head, *fast = head;while(slow->next && fast->next && fast->next->next){slow = slow->next;fast = fast->next->next;if(slow==fast){slow = head;while(slow!=fast){slow = slow->next;fast = fast->next;}return slow;}}return NULL;}
};