朋友们、伙计们，我们又见面了，本期来给大家解读一下leetcode中的第141道单链表OJ题，如果看完之后对你有一定的启发，那么请留下你的三连，祝大家心想事成！
数据结构与算法专栏：数据结构与算法
个 人 主 页 ：stackY、
C 语 言 专 栏：C语言：从入门到精通
LeetCode--141.环形链表：https://leetcode.***/problems/linked-list-cycle/description/
1.题目介绍
给你一个链表的头节点 head ，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 ，则返回 true 。 否则，返回 false 。
2.实例演示
3.题解思路
在这里如果使用最基础的方法来判断环形链表会比较麻烦，而且办法也不是很多，那么在这里小编给大家提供一种方法，依旧是我们熟悉的快慢指针的方法：
我们可以设置一个快指针和一个慢指针，如果有环，那么快指针和慢指针必定可以在环中相遇，因为快指针的速度始终是慢指针的2倍，所以快指针可以在环中追上慢指针，我们先来使用这种比较简便的方法，后面我们可以来验证一下：
代码演示：
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ bool hasCycle(struct ListNode *head) { //设置快慢指针 struct ListNode* slow = head; struct ListNode* fast = head; while(fast && fast->next) { //快指针一次走两步 fast = fast->next->next; //慢指针一次走一步 slow = slow->next; //如果在环中相遇就带环 if(fast == slow) { return true; } } //如果整个链表都走完了还是没有相遇则不带环 return false; }
这种方法看似简单，但是该如何证明呢？我们接着往下看：
4.拓展面试题
1. 假设有环，快指针一次走一步，慢指针一次走两步，快指针一定会追上慢指针吗？
快指针速度是慢指针的2倍，所以快指针先进环，慢指针后进环，我们假设快指针和慢指针相距为N，慢指针（slow）进环之后，快指针（fast）开始追击慢指针（slow），快指针一次走两步，慢指针一次走1步，那么它们的距离随着它们走的步数会逐渐的缩小1，就是一个公差为-1的等差数列，那么只要走的步数够多，快指针一定可以和慢指针相遇。
所以慢指针一次走一步，快指针一次走两步，一定会追上。
2. 假设有环，如果快指针走任意步数，慢指针走一步，快指针能追上慢指针吗？
在这里我们假设快指针一次走三步，慢指针一次走1步。
快指针速度是慢指针的3倍，所以快指针先进环，慢指针后进环，我们假设快指针和慢指针相距为N，慢指针（slow）进环之后，快指针（fast）开始追击慢指针（slow），快指针一次走3步，慢指针一次走1步，那么它们的距离随着它们走的步数会逐渐的缩小2，就是一个公差为-2的等差数列，这时我们需要计算一下它们之间的距离：
快慢指针的距离会随着步数的增加最后变为-1，这就表示会开始下一轮的追击，那么下一轮的追击就可以分为两种情况：
1. 假设环的周长为C，那么快慢指针的距离就变为了C-1，这时C-1如果为奇数，那么永远追不上。
2. 假设环的周长为C，那么快慢指针的距离就变为了C-1，这时C-1如果为偶数，那就就可以追上。
总结：
1. 快指针一次走一步，慢指针一次走两步，快指针一定会追上慢指针。
2. 如果快指针走任意步数，慢指针走一步，快指针不一定能追上慢指针。
朋友们、伙计们，美好的时光总是短暂的，我们本期的的分享就到此结束，最后看完别忘了留下你们弥足珍贵的三连喔，感谢大家的支持！
