强大，不动如山的强大，不会输给自己的真正的强大。
往期回顾：
数据结构——单链表
单链表力扣刷题
文章目录
经典例题：链表的中间结点
题目分析及双指针思路引入
双指针图解
leetcode 核心代码
判断环形链表——快慢指针延伸为追及问题
题目分析，图解
leetcode 核心代码
大家好，我是纪宁。
数据结构链表部分的面试、笔试大多都是在单链表部分，且大多题都是没有哨兵位的头结点，题目相数组通常比较难。这篇文章就给大家介绍一个单链表这里做题的常用技巧——快慢指针。
所谓快慢指针，就是有两个指针来维护单链表，通常定义为 slow 和 fast ，这两个指针遍历链表的速度不同。
经典例题：链表的中间结点
给你单链表的头结点 head ，请你找出并返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。
题目分析及双指针思路引入
在这个题中，如果要找的是数组中间元素的话，可能比较简单，直接计算出数组大小，再规定只遍历一半的内容即可。但是在链表，你除了知道当前结点的内容和下一节点的地址，一无所知，所以不能控制指针走的位置。
有一个特别巧妙的方法，就是定义两个指针，一个指针 slow 每次向后走一步， slow =slow->next；一个指针每次向后走两步，fast = fast -> next ->next ，这样，当指针 fast 或者 fast-> next 成为 NULL 指针的时候，slow 指针恰好走到了链表中间的位置，这样，就找到了链表的中间结点。
双指针图解
当链表长度为奇数时
当链表长度为偶数时
leetcode 核心代码
struct ListNode* middleNode(struct ListNode* head){
struct ListNode*slow,*fast;
slow=head;
fast=head;
while(fast!=NULL&&fast->next!=NULL)
{
fast=fast->next->next;
slow=slow->next;
}
return slow;
}
代码中要注意的一点是，因为fast 指针一次走‘两步’，所以循环的终止条件是 fast 或者 fast-> next 为空，最后返回 slow 指针。
判断环形链表——快慢指针延伸为追及问题
题目：给你一个链表的头节点 head ，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 ，则返回 true 。 否则，返回 false 。
题目分析，图解
如图：上面这个链表就是在 d3 进入环，d6的指针域指向d3，然后链表就会在 d3——d4——d5——d6——d3 这个环中循环。
首先，这道题没有给出进入环的位置，所以进环有很多种可能，这就排除了遍历链表的想法。这道题也可以使用快慢指针的方法，fast 指针和 slow 指针同时开始从头指针往后走，fast指针每次走两步，slow指针每次走1步，看这两个指针能否相遇。
如果链表带环，则快指针和慢指针一定会相遇，否则就不会相遇。这个追击原理类似于和你女朋友一起去操场跑圈，你们同时出发，只要你跑的比她快，并且你们在相遇前都不停，就一定能实现套圈。
所以，只要在指针 fast 和 指针 slow 往后走的时候，发现他们的指向相同（fast==slow）的时候，就说明链表带环（套圈了）。如果fast 或 fast->next 为空，说明链表遍历已经结束，链表不带环。
leetcode 核心代码
bool hasCycle(struct ListNode *head) {
struct ListNode *slow=head;
struct ListNode *fast=head;
while(fast&&fast->next)
{
slow=slow->next;
fast=fast->next->next;
if(fast==slow)
return true;
}
return false;
}
这就是博主给大家带来的单链表部分刷题的常用技巧——快慢指针，感谢观看。
