前言
最近看了labuladong的算法笔记，感觉对数据结构有有了一写新的理解，这里把链接放出来了
这篇文章旨在回顾我在看他笔记时所产生的一些想法，进行复盘，以加深我自己的记忆。
双指针介绍
首先， 双指针分为左右指针和快慢指针，而左右指针又分为左右向中间逼近和在中间向两侧逼近，
那么接下来我们分别对这些指针开始介绍。
左右指针
左右指针通常应用在数组中，为什么链表中应用少，应为链表是单向的话，是无法访问其前面节点的，需要靠额外的空间储存，即使是双向链表，我们也不知道其链表的长度是多少，必须进行一次遍历才能知道，所以在链表中不推荐左右指针。
两侧向中间移动
1.二分查找
int binarySearch(int[] nums, int target){
int left = 0, right = nums.length -1;
while(left < right) {
int mid = (left + right) /2;
if(target > nums[mid]) {
left = mid +1;
}else if(target < nums[mid]){
right = mid-1;
} else {
return target;
}
}
return null;
}2.两数之和
对于这道题，使用左右指针非常合适，首先声明左右指针索引位置，分别为0和nums.length-1，然后开一个while循环，只要两个指针不相遇，就一直执行while中的代码，循环通过左右指针位置，拿到指针位置在数组中的值，并且求和赋给sum，对sum进行判断。
- 如果直接等于目标值，那么直接返回索引数组，但要注意的是，题目所要求的下标索引是从1开始的，那么返回的就是
new int[]{left + 1, right + 1}, - 如果大于目标值，因为题目给的数组是有序的，那么通过有序这个性质，我们想要找到对应的目标值，就需要加一个更小的数，也就是使右指针向左移，即
right-- - 如果小于目标值，同理让加的值大一些，让左指针向右移，即
left++
int[] twoSum(int[] nums, int target) {
// 一左一右两个指针相向而行
int left = 0, right = nums.length - 1;
while (left < right) {
int sum = nums[left] + nums[right];
if (sum == target) {
// 题目要求的索引是从 1 开始的
return new int[]{left + 1, right + 1};
} else if (sum < target) {
left++; // 让 sum 大一点
} else if (sum > target) {
right--; // 让 sum 小一点
}
}
return new int[]{-1, -1};
}3.反转数组
使用左右指针可以进行反转数组，具体代码如下：
特别的：如果是字符数组，就可以实现反转字符串的效果了
void reverseArray(int[] nums){
int left = 0, right = nums.length -1;
while(left < right) {
int temp = nums[right];
nums[right] = nums[left];
nums[left] = temp;
left++;
right--;
}
}交换左右指针的位置的值，并且在交换后，使两个指针向中心逼近，不断反转，最后得到反转的数组。
4.回文串判断
回文串就是一个字符串正序与反序是一样的字符串，例如ababa。
实现代码如下：
boolean isPalindrome(String s) {
// 一左一右两个指针相向而行
int left = 0, right = s.length() - 1;
while (left < right) {
if (s.charAt(left) != s.charAt(right)) {
return false;
}
left++;
right--;
}
return true;
}这段代码非常简单，只需要判断左右指针位置的值是否相等就可以了，一旦不相等立马返回false，否则返回true。
中间向两侧移动
最长回文子串
如果想要判断一个字符串中最长的回文串，就需要使用从中间向两侧移动的左右指针：
String palindrome(String s , int l, int r ){
while(l>=0 && r< s.length && s.charAt(l) == s.charAt(r)){
l--;
r++;
//从中高级向两侧展开
}
}但是注意在寻找回文子串时，其长度可能为偶数也可能会为奇数，那么如何解决这个问题呢？
这时我们就需要指定左右指针的位置了，回文串长度为奇数时，只需要使l=r即可，同理当其为偶数时，使l+1=r即可。
对于这个问题，要先初始化一个空字符串，用来以后放置最长的回文子串，然后迭代寻找回文数，判断长度，长的就存放在res里。
String longestPalindrome(String s) {
String res = "";
for (int i = 0; i < s.length(); i++) {
// 以 s[i] 为中心的最长回文子串
String s1 = palindrome(s, i, i);
// 以 s[i] 和 s[i+1] 为中心的最长回文子串
String s2 = palindrome(s, i, i + 1);
res = res.length() > s1.length() ? res : s1;
res = res.length() > s2.length() ? res : s2;
}
return res;
}快慢指针
1.有序数组去重
定义一个快指针和一个慢指针，快指针的作用是用来探路，走在慢指针之前，
- 如果快指针位置所对应的值和慢指针所对应的值不一样，那么就是慢指针前进一位，并且将快指针的值赋给慢指针的值
- 如果值一样，那么慢指针不动，快指针继续向前走，直到走到和慢指针位置值不同的
- 最后有序数组去重后长度为慢指针的索引+1，即
slow+1
2.有序链表去重
原理是一样的，就不分析了
ListNode deleteDuplicates(ListNode head) {
if (head == null) return null;
ListNode slow = head, fast = head;
while (fast != null) {
if (fast.val != slow.val) {
// nums[slow] = nums[fast];
slow.next = fast;
// slow++;
slow = slow.next;
}
// fast++
fast = fast.next;
}
// 断开与后面重复元素的连接
slow.next = null;
return head;
}这里可能有读者会问，链表中那些重复的元素并没有被删掉，就让这些节点在链表上挂着，合适吗？
这就要探讨不同语言的特性了，像 Java/Python 这类带有垃圾回收的语言，可以帮我们自动找到并回收这些「悬空」的链表节点的内存，而像 C++ 这类语言没有自动垃圾回收的机制，确实需要我们编写代码时手动释放掉这些节点的内存。
不过话说回来，就算法思维的培养来说，我们只需要知道这种快慢指针技巧即可。 ——labuladong
3.移除元素
题目要求原地删除元素，那么只需要使用快慢指针改变数组元素即可
- 如果快指针的值不等于目标值，先让慢指针的值等于快指针的值，再让慢指针前进一位，就可以将等于目标值的位置替换为不为目标值的下一个值，以达到删除的目的。
- 如果快指针的值等于目标值，慢指针不动，等待不等于的值。
int removeElement(int[] nums, int val) {
int fast = 0, slow = 0;
while (fast < nums.length) {
if (nums[fast] != val) {
nums[slow] = nums[fast];
slow++;
}
fast++;
}
return slow;
}4.单链表的中点
要是正常的话就是遍历一次计算链表的长度n，再遍历一遍到n/2拿到中点，时间复杂度O(n^2)
但是使用快慢指针就可以使时间复杂度达到O(n)
具体思路为：慢指针走一步，快指针走两步，当快指针走到底时，慢指针正好到中点位置。
需要注意的是：当节点数为偶数时，中点返回的是靠后的一个节点。
ListNode middleNode(ListNode head) {
// 快慢指针初始化指向 head
ListNode slow = head, fast = head;
// 快指针走到末尾时停止
while (fast != null && fast.next != null) {
// 慢指针走一步，快指针走两步
slow = slow.next;
fast = fast.next.next;
}
// 慢指针指向中点
return slow;
}5.判断链表是否包含环
根据上述代码可得：
- 如果快指针走到空，那么这个链表就不包含环
- 如果快指针和慢指针相遇了，那么就说明有环
直接上代码boolean hasCycle(ListNode head) { // 快慢指针初始化指向 head ListNode slow = head, fast = head; // 快指针走到末尾时停止 while (fast != null && fast.next != null) { // 慢指针走一步，快指针走两步 slow = slow.next; fast = fast.next.next; // 快慢指针相遇，说明含有环 if (slow == fast) { return true; } } // 不包含环 return false; }
5.环形链表Ⅱ
快指针走2k步，慢指针走k步，快慢指针相遇时，两点交点为相遇点，此时设相遇点与起点位置相距m，那么头节点距环起点为k-m,又因为快节点是走了2k步，所以相遇点到环起点的距离也为k-m，也就是说只要让快或慢节点重置于头节点，再同时都一步一步走，当两指针相遇时的节点就是环起点。
以下为代码实现：
class Solution {
public ListNode detectCycle(ListNode head) {
ListNode fast, slow;
fast = slow = head;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
if (fast == slow) break;
}
// 上面的代码类似 hasCycle 函数
if (fast == null || fast.next == null) {
// fast 遇到空指针说明没有环
return null;
}
// 重新指向头结点
slow = head;
// 快慢指针同步前进，相交点就是环起点
while (slow != fast) {
fast = fast.next;
slow = slow.next;
}
return slow;
}
}总结
- 链表中通常使用快慢指针来进行对链表的操作
- 数组中两种指针都很常用
- 左右指针分为两种方向，一种从内向外，另一种从外向内
- 双指针可以把双循环转换成单循环
- 一般来讲，当遇到需要对一个数组进行重复遍历时，可以想到使用双指针法