一、顺序结构中的双指针法
顺序结构：这里主要指的是数组或字符串。
（1）普通数组
slow指向 当前所需元素数组的下一个空位。返回值为slow时，slow就代表目标数组的长度。
| 题目简述 | 关键点 | 解题思路 | 力扣题目 | 相关链接 |
|---|---|---|---|---|
| 删除数组中的某类元素 | 同向移动，快慢指针同时出发； | slow：指向当前所需元素数组的下一个空位。fast：遍历数组。 如果快指针遇到目标值则快指针直接跳过它一步，慢指针不动，如果快指针没有遇到目标值则将自己手中的数交给慢指针，然后各自前进一步。 | 27 移除元素（简单难度） | https://leetcode-cn.com/problems/remove-element/ |
| 移动数组中的某类元素到开头或者末尾 | 同向移动，快慢指针同时出发； | 如果快指针遇到目标值则快指针直接跳过它一步，慢指针不动，如果快指针没有遇到目标值则将自己手中的数和慢指针交换，然后各自前进一步。 | 283 移动零（简单难度） | https://leetcode-cn.com/problems/move-zeroes/ |
（2）有序数组
无序数组可以直接使用sort()函数排序后变成有序数组。sort(nums.begin(),nums.end())
| 题目简述 | 关键点 | 解题思路 | 力扣题目 | 相关链接 |
|---|---|---|---|---|
| 删除有序数组中的重复元素 | 同向移动，快指针先行一步，每次不断比较两个指针上的数是否相同。 | 一个指针（fast）从头到尾遍历，另一个（slow）始终指示当前没有重复的元素数组的下一个空位置；相同则快指针直接跳过去多行一步，不相同则快指针将手中的数交给慢指针，然后快慢指针同时前进一步；（这时慢指针指的是当前没有重复元素的最后一个*：注意返回值是slow+1。） | 26 删除排序数组中的重复项（简单难度） | https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array/ |
| 求有序数组中的众数（可能不止一个） | 同向移动，快指针先行一步，每次不断比较两个指针上的数是否相同。 | 相同则频率计时器+1，不相同则频率计时器设为0；每次检查频率计时器是否超过最大计数，超过则记录当前快指针上的数为众数。vector数组排序：sort(nums.begin(),nums.end()) | 169 多数元素（中等难度） | https://leetcode-cn.com/problems/majority-element/ |
| 将有序数组中每个元素平方后再排序 | 反向移动，左指针和右指针同时出发，每次比较左指针和右指针手上的数的平方； | 如果左指针手中数的平方更大则移动起始指针，如果末尾指针手中的数更大则移动末尾指针；当起始指针大于末尾指针时循环结束。（有序数组平方数组平方的最大值就在数组的两端，所以排序需要不断比较数组两端的数） | 977 有序数组的平方（简单难度） | https://leetcode-cn.com/problems/squares-of-a-sorted-array/ |
169 多数元素（中等难度）
1、排序法
众数是指在数组中出现次数大于⌊ n/2 ⌋ 的元素。 先将nums排序， ，然后返回中间元素的值即可（众数的个数大于一半，排好序的nums中间元素一定是众数） 。
1
2
3
4
5
6
7
class Solution {
public:
int majorityElement(vector<int>& nums) {
sort(nums.begin(),nums.end());
return nums[nums.size()/2];
}
};
2、摩尔投票法思路
候选人(cand_num)初始化为nums[0]，票数count初始化为1。 当遇到与cand_num相同的数，则票数count = count + 1，否则票数count = count - 1。 当票数count为0时，更换候选人，并将票数count重置为1。 遍历完数组后，cand_num即为最终答案。
为何这行得通呢？ 投票法是遇到相同的则票数 + 1，遇到不同的则票数 - 1。 且“多数元素”的个数> ⌊ n/2 ⌋，其余元素的个数总和<= ⌊ n/2 ⌋。 因此“多数元素”的个数 - 其余元素的个数总和 的结果 肯定 >= 1。 这就相当于每个“多数元素”和其他元素 两两相互抵消，抵消到最后肯定还剩余至少1个“多数元素”。
无论数组是1 2 1 2 1，亦或是1 2 2 1 1，总能得到正确的候选人。
作者：gfu 链接：https://leetcode-cn.com/problems/majority-element/solution/3chong-fang-fa-by-gfu-2/ 来源：力扣（LeetCode）
代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
int majorityElement(vector<int>& nums) {
int cand=nums[0],count=1;
for(int i=1;i<nums.size();i++){
if(cand==nums[i]){
count++;
}
else if(--count==0){
cand=nums[i];
count=1;
}
}
return cand;
}
};
二、非顺序结构中的双指针法
这里的非顺序结构主要指的是：链表或二叉树。
1、链表
链表删除某个元素的模板：
1、创建头结点和当前结点
2、删除结点
3、还原真实头结点，返回。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
ListNode* removeElements(ListNode* head, int val) {
//新建虚拟头结点
ListNode * myHead = new ListNode(0);
myHead->next=head;
//循环检查链表的当前节点的下一节点
ListNode* cur=myHead;//当前节点（一定不为空）
while (cur->next != NULL) {
if(cur->next->val == val) {
cur->next = cur->next->next;//删除下一节点
} else {
cur = cur->next;//更新当前节点为下一节点
}
}
//还原真实头结点
head = myHead->next;
return head;
}
（1）链表的删除操作
有序链表中删除一个节点cur需要其前一个节点pre->next=cur->next; 所以其天生需要节点的先后关系。
所以在执行删除操作时，一般就需要(头结点)
| 题目简述 | 关键点 | 解题思路 | 力扣题目 | 相关链接 |
|---|---|---|---|---|
| 删除链表中的某类元素（简单难度） | 虚拟头结点；链表的循环操作和节点的删除操作 | 同向移动，快指针从头结点先行一步，每次判断快指针是否符合删除条件，若符合则删除快指针并且重新为快指针赋值；否则则快指针和慢指针都前进一步。 | 203 移除链表元素（简单难度） | https://leetcode-cn.com/problems/remove-linked-list-elements/ |
| 删除链表的倒数第N个节点（中等难度） | 快指针先走N步之后进行判断 | 同向出发，快指针从头结点先行N步，如果此时快指针不存在则直接返回，若存在则快指针和慢指针（从头结点）同时出发，当快指针不存在时删除慢指针之后的一个节点。 | 19 删除链表的倒数第N个节点（中等难度） | https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/ |
19.删除链表的倒数第n个结点
（1）假设链表长度为m+n。
fast、slow开始指向虚拟头结点。
1、fast先走n步
2、fast和slow同时走，直到fast指向链表的最后一个。
则slow走了m步。
（2）链表的删除操作，需要得到目标结点的前一个结点。
所以
1、fast先走n+1步。
2、fast和slow同时走，直到fast指向链表的最后一个的下一个位置：NULL。
则slow走了m-1步，在倒数第n个结点前。
（2）链表的反转操作
###
| 题目简述 | 关键点 | 解题思路 | 力扣题目 | 相关链接 |
|---|---|---|---|---|
| 将一个链表全部反转过来 | 相邻节点之间的反转操作 | 同向移动，快指针从头结点先行一步；每次移动快节点和慢节点都进行一次反向 | 206 反转链表（简单难度） | https://leetcode-cn.com/problems/reverse-linked-list/ |
| 将一个链表中的[left,right]区域反转过来 | 慢指针从虚拟头结点出发找到第left个节点，然后快指针从慢指针的后一个节点出发，共同前进找到第right个节点 | 92 反转链表II（中等难度） | https://leetcode-cn.com/problems/reverse-linked-list-ii/ | |
| 根据快慢指针找到中点；反转后半段；比较前后两端节点值 | 234 回文链表（简单难度） | https://leetcode-cn.com/problems/palindrome-linked-list/ |
###
206、反转链表
1、保存后面链表
2、断开指针
3、重新规划pre、cur
234、回文链表
1、慢指针走一步，快指针走两步
2、pre记录慢指针的前一个，用来分割链表，如果链表长度为奇数，则后半部分多一个结点。
3、将后半部分反转，得cur2，前半部分为cur1.
4、按照cur1的长度，比较cur1和cur2的节点数值。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
class Solution {
public:
bool isPalindrome(ListNode* head) {
ListNode* slow=head;
ListNode* fast=head;
ListNode* pre=head;
//慢指针走一步，快指针走两步
while(fast && fast->next){
pre=slow;
slow=slow->next;
fast=fast->next->next;
}
//pre断开链表
pre->next=NULL;
ListNode* cur1=head;
//反转cur2
ListNode* cur2=reverselist(slow);
//按照cur1的长度，比较cur1，cur2
while(cur1){
if(cur1->val!=cur2->val){
return false;
}
cur1=cur1->next;
cur2=cur2->next;
}
return true;
}
ListNode* reverselist(ListNode* head){
ListNode* cur=head;
ListNode* temp=head;
ListNode* pre=NULL;
while(cur){
//保存后面链表
temp=cur->next;
//断开原链表
cur->next=pre;
//重新规划pre，cur
pre=cur;
cur=temp;
}
return pre;
}
};