提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档
文章目录 前言一、什么是快慢指针二、例题体现三、数组模拟链表总结
前言
在leetcode刷题经常会碰到快慢指针问题，本文将快慢指针的题目总结模板
一、什么是快慢指针快慢指针其实就是定义两个指针 fast 和 slow 然后让fast每次都比slow走快一步。快慢指针常见在链表题目，快慢指针的出现让我们能更好的定位链表中的结点位置，也可以在一些特定数组中模拟成链表，简化题目难度。
二、例题体现在leetcode中有这么一个题目，求环形链表的位置，题目链接环形链表II
这个题目就是典型的快慢指针题型，在这个题目中有两个难点，第一个就是判断链表有无环，在链表有无环判断就是用快慢指针，fast每次走两步，slow每次走一步，如果fast会与slow相遇，那么就证明链表中存环，第二个难点就是找到出现环路的结点。
那环路结点怎么求呢？让我们先来分析下在fast和slow在图中走的路线(图片来源leetcode官网),首先我们假设链表中环外部分的长度为 a。slow 指针进入环后，又走了 b 的距离与 fast 相遇，此时fast已经走了n圈了，所以slow走的距离是 a + b，fast走了 a + (n+1)b + nc 又因为，fast每次比slow多走一部，所以2slow==fast 则 我们可以推出 a + (n+1)b + nc == 2（a+b）
所以现在我们可以推出 a+(n+1)b+nc=2(a+b)⟹a=c+(n−1)(b+c)，下面图是这个推导过程
有了 a=c+(n-1)(b+c) 的等量关系，我们会发现：从相遇点到入环点的距离加上 n−1 圈的环长，恰好等于从链表头部到入环点的距离。
因此，当发现slow 与 fast 相遇时 ，只需要让fast = head ，让fast从头开始走，他们再次相遇的点就是环形结点。
下面是一些类似题目，开始练手吧！！
环形链表I
链表的中间结点
class Solution {public: ListNode* middleNode(ListNode* head) { ListNode *fast = head,*slow = head; while(fast&&fast->next){ fast = fast->next->next; slow = slow->next; } return slow; }};剑指offer22.链表中倒数第k个结点
class Solution {public: ListNode* getKthFromEnd(ListNode* head, int k) { ListNode *fast = head,*slow = head; while(fast&&k--){ fast = fast->next; } while(fast){ fast = fast->next; slow = slow->next; } return slow; }};快慢指针+反转链表
class Solution {public: ListNode *reverseList(ListNode *head){ ListNode *pre = NULL,*cur = head; while(cur) { ListNode *next = cur->next; cur->next = pre; pre = cur; cur = next; } return pre; } bool isPalindrome(ListNode* head) { if (head == NULL) { return true; } ListNode *fast = head,*slow = head; while(fast->next&&fast->next->next){ fast = fast->next->next; slow = slow->next; } ListNode *h = reverseList(slow->next); bool flag = true; ListNode* p1 = head,*p2 = h; while(flag&&p2){ if(p1->val != p2->val) flag = false; p1 = p1->next; p2 = p2->next; } slow->next = reverseList(h); return flag; }}; 三、数组模拟链表寻找重复数
这个题目比较灵活，想要实现数组模拟链表的情况，必须满足数组中的数字都是在 1 到 n 之间的(在数组中进行游走不会越界),因为有重复数字的出现, 所以这个游走必然是成环的, 环的入口就是重复的元素。只是改变一下数据存储状态，思路和上面的例子完全一样。
本文总结了快慢指针的一些用法和延伸，希望能帮助到大家。