一、双指针法的特点

一般双指针法有以下2个优点：

1、一般在原来的内存空间上操作，很少添加额外的内存空间；

2、一般只需要循环一次，时间复杂度大幅下降。

一般双指针法有以下2种表现方式：

1、同向移动：在同向移动时，指针互相之间间隔1个距离进行移动；

2、相向移动：在相向移动中，双指针一个指针在开头，另外一个指针在结尾，根据满足的条件进行移动指针；

二、顺序结构中的双指针法

这里主要指的是数组或字符串

（1）普通数组

题目简述	关键点	解题思路	力扣题目	相关链接
删除数组中的某类元素	同向移动，快慢指针同时出发；	如果快指针遇到目标值则快指针直接跳过它一步，慢指针不动，如果快指针没有遇到目标值则将自己手中的数交给慢指针，然后各自前进一步。	27 移除元素（简单难度）	https://leetcode-cn.com/problems/remove-element/
移动数组中的某类元素到开头或者末尾	同向移动，快慢指针同时出发；	如果快指针遇到目标值则快指针直接跳过它一步，慢指针不动，如果快指针没有遇到目标值则将自己手中的数和慢指针交换，然后各自前进一步。	283 移动零（简单难度）	https://leetcode-cn.com/problems/move-zeroes/

（2）有序数组

提示：无序数组可以直接使用sort()函数排序后变成有序数组

题目简述	关键点	解题思路	力扣题目	相关链接
删除有序数组中的重复元素	同向移动，快指针先行一步，每次不断比较两个指针上的数是否相同。	相同则快指针直接跳过去多行一步，不相同则快指针将手中的数交给慢指针，然后快慢指针同时前进一步；	26 删除排序数组中的重复项（简单难度）	https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array/
求有序数组中的众数（可能不止一个）	同向移动，快指针先行一步，每次不断比较两个指针上的数是否相同。	相同则频率计时器+1，不相同则频率计时器设为0；每次检查频率计时器是否超过最大技术，超过则记录当前快指针上的数为众数	169 多数元素（中等难度）	https://leetcode-cn.com/problems/majority-element/
将有序数组中每个元素平方后再排序	反向移动，左指针和右指针同时出发，每次比较左指针和右指针手上的数的平方；	如果左指针手中数的平方更大则移动起始指针，如果末尾指针手中的数更大则移动末尾指针；当起始指针大于末尾指针时循环结束。（有序数组平方数组平方的最大值就在数组的两端，所以排序需要不断比较数组两端的数）	977 有序数组的平方（简单难度）	https://leetcode-cn.com/problems/squares-of-a-sorted-array/

三、非顺序结构中的双指针法

这里主要指的是链表或二叉树

1、链表

链表的遍历模板

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/

（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/

（3）环形链表的操作

题目简述	关键点	解题思路	力扣题目	相关链接
		快慢指针，若指针相遇则判断有环	141 环形链表（简单难度）	https://leetcode-cn.com/problems/linked-list-cycle/
		指针环内相遇后，两个节点分别从head和相遇点出发，再次相遇点即是环入口	142 环形链表II（中等难度）	https://leetcode-cn.com/problems/linked-list-cycle-ii/

（4）两条链表是否相交

题目简述	关键点	解题思路	力扣题目	相关链接
		快慢指针，若指针相遇则判断有环	141 环形链表（简单难度）	https://leetcode-cn.com/problems/linked-list-cycle/
		指针环内相遇后，两个节点分别从head和相遇点出发，再次相遇点即是环入口	142 环形链表II（中等难度）	https://leetcode-cn.com/problems/linked-list-cycle-ii/