算法中的双指针使用，有时候会觉得很巧妙，解决了很多的问题，有必要归纳总结一下，首先双指针也是个很宽泛的概念，它类似于遍历中的 i 和 j 但是其区别是，两个指针是同时移动的，即没有贡献复杂度从O(N) 到 O(N*N) ，所以被很多算法大佬所推崇，所以基于此归纳总结出双指针的常见解法和套路。

1、题型归纳

这里将题型归纳为四种，分别如下：

• 快慢指针（前后按不同步调的两个指针）
• 前后双端指针（一个在首，一个在尾部，向中间靠拢）
• 固定间隔的指针（以i, i + k的间距的两个指针）

前面讲到，这三种指针都是遍历一次数组即可完成，其时间复杂度低于或者等于O(N) ，空间复杂度是O(1) 因为就两个指针存储。

滑动窗口（有两个指针，一个在前一个在后，不断滚动）

• 滑动窗口算法可以用以解决数组/字符串的子元素问题
• 滑动窗口算法可以将嵌套的for循环问题，转换为单循环问题，降低时间复杂度

2、快慢指针

快慢指针一般都初始化指向链表的头结点 head，前进时快指针 fast 在前，慢指针 slow 在后，巧妙解决一些链表中的问题。

第一题：判断链表是否有环

这应该属于链表最基本的操作了，如果读者已经知道这个技巧，可以跳过。

单链表的特点是每个节点只知道下一个节点，所以一个指针的话无法判断链表中是否含有环的。

如果链表中不含环，那么这个指针最终会遇到空指针 null 表示链表到头了，这还好说，可以判断该链表不含环。

boolean hasCycle(ListNode head) {
    while (head != null)
        head = head.next;
    return false;
}

但是如果链表中含有环，那么这个指针就会陷入死循环，因为环形数组中没有 null 指针作为尾部节点。

经典解法就是用两个指针，一个跑得快，一个跑得慢。如果不含有环，跑得快的那个指针最终会遇到 null，说明链表不含环；如果含有环，快指针最终会超慢指针一圈，和慢指针相遇，说明链表含有环。

boolean hasCycle(ListNode head) {
    ListNode fast, slow;
    fast = slow = head;
    while (fast != null && fast.next != null) {
        fast = fast.next.next;
        slow = slow.next;
        if (fast == slow) return true;
    }
    return false;
}

第二题：寻找链表的中间节点

题目描述：

给定一个头节点为 head 的非空单链表，返回链表的中间节点。

如果有两个中间节点，则返回第二个中间节点。 示例:

输入：[1,2,3,4,5] 输出：此列表中的节点 3

思路分析:

要找到链表的中间节点，可以定义两个指针，一个是慢指针slow，另一个是快指针fast。初始，慢指针slow和快指针fast都指向链表的头节点。然后，快指针fast每次向前移动两步，慢指针slow每次向前移动一步，当快指针fast不能继续向前移动时，慢指针slow所指的节点就是中间节点。

对于节点个数为奇数的链表来说，其中间节点只有一个；而对于节点个数为偶数的链表来说，其中间节点有两个。

接着，我们就通过动画来看下如何通过快慢指针找到链表的中间节点。

1.当快指针fast向前移动的条件是：fast.next!=null && fast.next.next != null时：

对于节点个数为奇数的链表来说，动画演示如下，此时链表的中间节点是节点3。

• 对于节点个数为偶数的链表来说，动画演示如下，此时链表的中间节点是节点2，即在2和3这两个中间节点中，找到是第一个中间节点。

2.当快指针fast向前移动的条件是：fast!=null && fast.next != null时： 对于节点个数为奇数的链表来说，动画演示如下，此时链表的中间节点是节点3。

对于节点个数为偶数的链表来说，动画演示如下，此时链表的中间节点是节点3，即在2和3这两个中间节点中，找到是第二个中间节点。

题目要求的是如果有两个中间节点，则返回第二个中间节点。因此，对于该题目而言，快指针fast向前移动的条件是：fast!=null && fast.next != null。 代码实现：

public static ListNode midNode(ListNode head){
        ListNode slow=head,fast=head;
        while(fast!=null&&null!=fast.next){
            fast=fast.next.next;
            slow=slow.next;
        }
        return slow;
    }

结束。

第三题：已知链表有环返回环的起始位置

先看一下推导过程:

假设从头结点到环形入口节点 的节点数为x。
环形入口节点到 fast指针与slow指针相遇节点 节点数为y。
从相遇节点 再到环形入口节点节点数为 z。 如图所示：

那么相遇时：
slow指针走过的节点数为: x + y
fast指针走过的节点数： x + y + n (y + z)，n为fast指针在环内走了n圈才遇到slow指针， （y+z）为 一圈内节点的个数
因为fast指针是一步走两个节点，slow指针一步走一个节点， 所以 fast指针走过的节点数 = slow指针走过的节点数 * 2
(x + y) * 2 = x + y + n (y + z)，两边消掉一个（x+y）: x + y = n (y + z)因为我们要找环形的入口，那么要求的是x，因为x表示 头结点到 环形入口节点的的距离。所以我们要求x ，将x单独放在左面：x = n (y + z) - y，在从n(y+z)中提出一个 （y+z）来，整理公式之后为如下公式：x = (n - 1) (y + z) + z 注意这里n一定是大于等于1的，因为 fast指针至少要多走一圈才能相遇slow指针。
这个公式说明什么呢，先拿n为1的情况来举例，意味着fast指针在环形里转了一圈之后，就遇到了 slow指针了。
当 n为1的时候，公式就化解为 x = z,这就意味着，从头结点出发一个指针，从相遇节点 也出发一个指针，这两个指针每次只走一个节点， 那么当这两个指针相遇的时候就是 环形入口的节点。也就是在相遇节点处，定义一个指针index1，在头结点处定一个指针index2。让index1和index2同时移动，每次移动一个节点， 那么他们相遇的地方就是 环形入口的节点。
那么 n如果大于1是什么情况呢，就是fast指针在环形转n圈之后才遇到 slow指针。
其实这种情况和n为1的时候 效果是一样的，一样可以通过这个方法找到 环形的入口节点，只不过，index1 指针在环里 多转了(n-1)圈，然后再遇到index2，相遇点依然是环形的入口节点。

补充

在推理过程中，大家可能有一个疑问就是：为什么第一次在环中相遇，slow的 步数 是 x+y 而不是 x + 若干环的长度 + y 呢？

首先slow进环的时候，fast一定是先进环来了。如果slow进环入口，fast也在环入口，那么把这个环展开成直线，就是如下图的样子：

可以看出如果slow 和 fast同时在环入口开始走，一定会在环入口3相遇，slow走了一圈，fast走了两圈。重点来了，slow进环的时候，fast一定是在环的任意一个位置，如图：

那么fast指针走到环入口3的时候，已经走了k + n 个节点，slow相应的应该走了(k + n) / 2 个节点。因为k是小于n的（图中可以看出），所以(k + n) / 2 一定小于n。也就是说slow一定没有走到环入口3，而fast已经到环入口3了。
这说明什么呢？
在slow开始走的那一环已经和fast相遇了。那有同学又说了，为什么fast不能跳过去呢？ 在刚刚已经说过一次了，fast相对于slow是一次移动一个节点，所以不可能跳过去。

代码如下：

public static ListNode detectCycle(ListNode head) {
        if(head==null){
            return null;
        }
        //快慢指针都指向头节点
        ListNode slow=head,fast=head;
        //链表存在环，并且快慢指针没有相遇，直到相遇的时候才结束循环
        while(fast!=null){
            //因为fast一次走两步，这里一定是先判断fast是否null，fast不为null才看fast.next
            //只有两者同不为null的时候，才说明有环
            if(null!=fast.next){
                fast=fast.next.next;
            }else{
                return null;
            }
            slow=slow.next;
            //注意这个条件不能放在第一个while循环中，因为初始化的时候slow和fast都为null
            if(fast==slow){
                //如果快指针和慢指针相遇，则令快指针从头开始一步一步走，直到再次和慢指针相遇就是环的入口
                fast=head;
                while(fast!=slow){
                    fast=fast.next;
                    slow=slow.next;
                }
                break;
            }
        }
        //此时如果链表有环，则一定是找到环的入口跳出来的，如果链表没有环，fast会走到最后变为null
        return fast;
    }

第四题：反转链表

题目描述：

反转一个单链表，这里主要是使用了三个指针，分别是指向当前节点cur和当前节点前一个节点pre以及当前节点的下一个节点nextNode，只有三个指针才能实现链表反转而不断链。 示例:

输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL
思路分析：

代码实现：

//反转链表，返回反转后链表的头节点
    public static ListNode reverseLink(ListNode head){
        if(head==null||head.next==null){
            //如果只有一个节点的链表，或者是空链表,就直接返回
            return head;
        }
        ListNode pre=null; //当前节点的前一个节点
        ListNode cur=head; //当前节点为head，从头节点开始反转
        ListNode nextNode =null; //当前节点的后一个节点
        //反转结束的条件为当前节点是否为null ,如果当前节点指向null说明反转结束了
        while(cur!=null){
            //为了防止断链，反转之前需要先记录当前节点的下一个节点
            nextNode=cur.next;
            //反转
            cur.next=pre;
            //反转之后需要向前移动，继续反转
            //注意：这里一定是先将pre前移，如果先一定cur，则pre就指向了后面的后面节点。
            pre=cur;
            cur=nextNode;
        }
        //最后返回的是pre，因为当前节点cur已经到null了，此时pre刚好在反转节点的最后一个，也就是新的头节点
        return pre;
    }

到此结束。

第五题：重排链表

题目描述：

给定一个单链表 L：L0→L1→…→Ln-1→Ln ，

将其重新排列后变为：L0→Ln→L1→Ln-1→L2→Ln-2→…

你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

示例:

给定链表 1->2->3->4->5, 重新排列为 1->5->2->4->3.

思路分析:

通过观察给到的示例，其结果是将原链表的前半部分和原链表的后半部分反转之后的链表进行合并得到的。

因此，整体思路就是：

• 首先，找到链表的中间节点

• 接着，将链表的后半部分反转

• 然后，将链表的前半部分和链表的后半部分反转后的结果进行合并。

示例1给出的链表结构如下：

完整代码实现如下：

3、左右指针

左右指针在数组中实际是指两个索引值，一般初始化为 left = 0, right = nums.length - 1 。

第一题：二分查找

这里只写最简单的二分算法，旨在突出它的双指针特性：

int binarySearch(int[] nums, int target) {
    int left = 0; 
    int right = nums.length - 1;
    while(left <= right) {
        int mid = (right + left) / 2;
        if(nums[mid] == target)
            return mid; 
        else if (nums[mid] < target)
            left = mid + 1; 
        else if (nums[mid] > target)
            right = mid - 1;
    }
    return -1;
}

第二题：两数之和

直接看一道 LeetCode 题目吧：

只要数组有序，就应该想到双指针技巧。这道题的解法类似二分查找，通过调节 left 和 right 可以调整 sum 的大小：

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};
}

第三题：反转数据

以下是代码：

void reverse(int[] nums) {
    int left = 0;
    int right = nums.length - 1;
    while (left < right) {
        // swap(nums[left], nums[right])
        int temp = nums[left];
        nums[left] = nums[right];
        nums[right] = temp;
        left++; right--;
    }
}

这个是针对数组的反转。

4、固定间隔的指针

快指针和慢指针中间间隔k个距离。

第一题：寻找链表倒数第k个元素

我们的思路还是使用快慢指针，让快指针先走 k 步，然后快慢指针开始同速前进。这样当快指针走到链表末尾 null 时，慢指针所在的位置就是倒数第 k 个链表节点（为了简化，假设 k 不会超过链表长度）：

ListNode slow, fast;
slow = fast = head;
while (k-- > 0) 
    fast = fast.next;

while (fast != null) {
    slow = slow.next;
    fast = fast.next;
}
return slow;

第二题：删除链表倒数第n个元素

 *  给定一个链表，删除链表的倒数第n个节点并返回链表的头指针
 * 例如，
 *  给出的链表为:1->2->3->4->5, n= 2.
 *  删除了链表的倒数第n个节点之后,链表变为1->2->3->5.

public static ListNode removeNthFromEnd (ListNode head, int n) {
        if (head==null){
            return null;
        }
        ListNode fast=head;
        ListNode res=new ListNode(0);
        res.next=head; //这是一个哑节点，便于删除,相当于在head之前加了一个节点
        ListNode slow=res;
        //快指针先走n步
        while(n>0){
            fast=fast.next;
            n--;
        }
        //快慢指针同时走，如果快指针到最后一个节点，则慢指针位于倒数第n个节点的前一个节点
        while(fast!=null){
            fast=fast.next;
            slow=slow.next;
        }
        //删除slow.next，也就是第n个元素
        slow.next=slow.next.next;
        //返回删除之后的结果，注意，这里要把哑节点去掉
        return res.next;
    }

以上代码经过测试可行。

5、滑动窗口

左右指针中间的内容相当于是一个窗口，不断移动左右指针，实现窗口的滑动。

第一题：无重复字符的最大子串

没有重复字符的子字符的最大长度：给一个字符串，获得没有重复字符的最长子字符的长度
例子：
输入："abcabcbb"
输出：3
解释：因为没有重复字符的子字符是'abc'，所以长度是3

滑动窗口算法：

通过使用HashSet作为一个滑动窗口，检查一个字符是否已经存在于现有的子字符中只需要O(1).
滑动窗口经常用来处理数组/字符串问题。窗口代表着一组数据/字符串元素，通过开头和结尾的索引来定义窗口。

//简单的滑动窗口方式，可能时间复杂度可能会高一点
    public static int lengthOfLongestSubstring3(String s){
        int n=s.length();
        int l=0,r=0; //初始化左右指针均为0
        int count=0;
        HashSet<Character> set = new HashSet<>();
        //循环的条件是左右指针均不能大于字符串的长度
        while(r<n&&l<n){
            if(!set.contains(s.charAt(r))){
                //如果不包含右节点，则添加到set集合中
                set.add(s.charAt(r));
                //重新计算最长的子串
                count=Math.max(count,r-l+1);
                //右节点向前移动一位
                r++;
            }else{
                //如果包含右节点，就需要移动窗口，这里移除左节点，相当于在更新窗口的起始位置
                //如果不移除节点，右边一旦卡住，则右节点就用于停在了那里，左节点会一直循环到最后。
                set.remove(s.charAt(l));
                //左指针向前一步走
                l++;
            }
        }
        return count;
    }

分析：时间复杂度：O(2n)。在最差的情况下，每个字符将会被访问两次

优化的窗口算法：

上面的滑动窗口算法最多需要2n的步骤，但这其实是能被优化为只需要n步。我们可以使用HashMap定义字符到索引之间的映射，然后，当我们发现子字符串中的重复字符时，可以直接跳过遍历过的字符了。

public static int lengthOfLongestSubstring4(String s){
        int n=s.length();
        int count=0;
        Map<Character, Integer> map = new HashMap<>();
        for (int r = 0,l=0; r < n; r++) {
            if(map.containsKey(s.charAt(r))){
            //如果map中已经存在当前字符，说明该字符是重复字符，则左指针可以直接跳到该字符的后面的一个位置
                l=Math.max(map.get(s.charAt(r)),l);
            }
            //重新计算大小
            count=Math.max(count,r-l+1);
            //把该字符添加到map中，并且设置其位置为r+1,这是为了方便左指针跳转时跳过重复字符所在的位置
            //注意，这里字符为键，其索引+1位值，相同的字符重复认为是一个键，此时put只会更新值
            map.put(s.charAt(r),r+1);
        }
        return count;
    }