数组

首先先复习一下 快慢指针 的套路：

int slow = 0, fast = 0;
while(fast < nums.length){
    if ( ... ){
        // todo 缩小范围
        slow++;
    }
    // todo ... 扩大范围
    fast++;
}

下面根据上面的模板，给出几道来自leetcode算法题：

删除有序数组中的重复项

给你一个 非严格递增排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。

public int removeDuplicates(int[] nums) {
    // 定义一下两个变量（快慢指针）
    int slow = 0, fast = 0;
    // 变量边界范围
    while(fast < nums.length){
        if (nums[fast] != nums[slow]){
            // 缩小范围
            slow++;
            nums[slow] = nums[fast];
        }
        // 默认一直都在扩大范围
        fast++;
    }
    return slow+1;
}

最长连续递增序列

给定一个未经排序的整数数组，找到最长且 连续递增的子序列，并返回该序列的长度。

连续递增的子序列 可以由两个下标 l 和 r（l < r）确定，如果对于每个 l <= i < r，都有 nums[i] < nums[i + 1] ，那么子序列 [nums[l], nums[l + 1], ..., nums[r - 1], nums[r]] 就是连续递增子序列。

思路分析：题目要求我们找的子序列是 连续 的，并且子序列里的元素要求 严格单调递增。在遍历的时候，从第 2 个元素开始;

• 如果当前遍历到的元素比它左边的那一个元素要严格大，「连续递增」的长度就加 1;
• 否则「连续递增」的起始位置就需要重新开始计算。

public int findLengthOfLCIS(int[] nums) {
    // 定义快慢指针变量
    int slow = 0, fast = 0;
    // 定义长度变量
    int res = 1;
    // 遍历边界范围
    while (fast < nums.length){
        if (fast > 0 && nums[fast-1] >= nums[fast]){
            res = Math.max(res,fast-slow);
            slow = fast;
        }
        fast++;
    }
    return Math.max(fast-slow,res);
}

链表

对于对链表而言，其实思想是一样的，其大致框架就是将数组替换成了链表而已。

// 定义快慢指针
ListNode slow = head, fast = head;
// 对于快慢指针，我们需要考虑的就是快指针不要越界
while (快指针的范围){
    fast = fast.next.next;
    slow = slow.next;
    // 结束条件
    if (结束条件){
        // todo 操作
    }
}

环形链表

给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

如果链表中存在环 ，则返回 true 。 否则，返回 false 。

public boolean hasCycle(ListNode head) {
    // 考虑特殊情况：只有一个元素 不存在元素 时，一定不会有循环
    if (head == null || head.next == null){
        return false;
    }
    // 定义快慢指针
    ListNode slow = head, fast = head;
    // 对于快慢指针，我们需要考虑的就是快指针不要越界
    while (fast != null && fast.next != null){
        fast = fast.next.next;
        slow = slow.next;
        // 结束条件：快指针 = 慢指针
        if (fast == slow){
            return true;
        }
    }
    // 如果快指针有结束情况，说明一定不循环
    return false;
}

注意：为什么不是先判断 if (fast == slow) 而是 先移动指针？ 其实答案挺明显的，如果我们先判断，那么就算是无环的时候，你也会发现fast == slow,那这不就一直返回 true 了嘛，显然不合理。

删除链表的倒数第 N 个结点

题目：

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

示例 1：

输入：head = [1,2,3,4,5], n = 2

输出：[1,2,3,5]

示例 2：

输入：head = [1], n = 1

输出：[]

示例 3：

输入：head = [1,2], n = 1

输出：[1]

提示：

• 链表中结点的数目为 sz
• 1 <= sz <= 30
• 0 <= Node.val <= 100
• 1 <= n <= sz

进阶：你能尝试使用一趟扫描实现吗？

public ListNode removeNthFromEnd(ListNode head, int n) {
    if(head == null) return head;
    ListNode dummy = new ListNode(-1);
    dummy.next = head;
    ListNode slow = dummy, fast = dummy;
    while(n > 0){
        fast = fast.next;
        n--;
    }
    while(fast.next != null){
        slow = slow.next;
        fast = fast.next;
    }
    slow.next = slow.next.next;
    slow = slow.next;
    return dummy.next;
}

链表的中间结点

对于链表而言，找中点，判断是否是回文，其实都是可以使用快慢指针实现的。

下面再看一下这道找中点的题目，其实就是快指针每次移动的速度都是慢指针的两倍：

题目 给你单链表的头结点 head ，请你找出并返回链表的中间结点。

如果有两个中间结点，则返回第二个中间结点。

示例 1：

输入：head = [1,2,3,4,5]

输出：[3,4,5]

解释：链表只有一个中间结点，值为 3 。

示例 2：

输入：head = [1,2,3,4,5,6]

输出：[4,5,6]

解释：该链表有两个中间结点，值分别为 3 和 4 ，返回第二个结点。

public ListNode middleNode(ListNode head) {
    if(head == null || head.next == null){
        return head;
    }
    ListNode slow = head, fast = head;
    while(fast.next != null && fast.next.next != null){
        slow = slow.next;
        fast = fast.next.next;
    }
    if(fast.next != null){
        return slow.next;
    }else{
        return slow;
    }
}

总结

本章的快慢指针到整理就结束了，总结一下快慢指针的使用场景：

• 数组
• 链表

上面两种类型是比较常见的。

快慢指针主要思想就是通过两个指针，一前一后去判断。与二分查找不同。二分查找是首尾（左右）两个指针。

快慢指针可以解决：

• 循环问题
• 重复问题
• 最值问题（长度，一般争对数组）