找我一起玩0v0
很高兴你能关注到我，记得有空可以来找我玩鸭。
455 字
2 分钟
环形链表
环形链表(快慢跑)
开头放链接力扣141题环形链表
引入
如何判断一个链表有环，就好比是在判断是直线的跑道还是环形的跑道
直线跑道示例:
环形跑道示例:
思考
此时我们设想以下两个场景:
-
在50米跑的时候，有一个跑的比你快的人，那他肯定先到了终点，也就意味着，你在起点是唯一一次见到他的机会
-
但是在1000米跑的时候，如果有人比你快，那他就可能超过你整整一圈，所以你可以在赛中二次见到他
注：这里的50米跑和1000米跑并非指的是跑道长度，而是想指出用的是直线跑道还是环形跑道
至此，我们可以得出以下结论，当我们不知道跑道长度和跑道类型的情况下：
-
如果是直线跑道，只要双方速度不一，即使跑道很长，两人永远不会相遇
-
如果是环形跑道，只要双方速度不一，即使跑道很短，两人总会相遇
结论
即链表有环的情况下，若双指针以不同的步长遍历时，总会有一次双指针指向同一内存空间
代码实现
struct ListNode { //链表数据结构 int val; ListNode *next;
ListNode(int x) : val(x), next(NULL) {}};
class Solution {public: bool hasCycle(ListNode *head) { auto *h1 = head; //跑的慢的 auto *h2 = head; //跑的快的 bool flag = false; //是否在赛中遇上了 while (h1 != nullptr && h2 != nullptr) { h1 = h1->next; //慢的每次跑1格 if (h2->next != nullptr) { h2 = h2->next->next; //快的每次跑两格 } else break; if (h1 == h2){ //当h1==h2就找到了 flag = true; break; } } return flag; }};