校招刷题群
高效刷题 迎战校招
校招精选试题
近年面笔经面经群内分享
Java刷题群 前端刷题群 产品运营群
首页 > 算法 > 链表算法
题目

单链表中是否有环,写出代码

解答

思路

1、一个指针只能遍历,没有办法做出判断

2、尝试两个结点,两个结点通常是slow走一步,fast走两步

3、通过画图或者思考,可以看出,有环的情况下(必须要明白以下):

slow,fast都进入环中,fast因为走得快,fast每步都能追赶1个与slow的距离,n步后,会相遇。

拿跑步来说,slow跑一圈,fast就能跑两圈,一定能赶上。

所以当两者相遇时,slow没跑完一圈,fast不会跑超过两圈。

代码

核心代码
bool isExitsLoop(Node head)
{
Node slow = head;
Node fast = head; 

while ( fast && fast.next )
{
slow = slow.next;
fast = fast.next.next;
if ( slow == fast ) break;
}
return !(fast == null || fast.next == null);
}
C 7条回复 评论
望岳

大佬,能转载下吗?

发表于 2021-12-15 21:00:00
0 0
书为

我想咨询下,如果是做产品经理,考研可以考哪些相关专业

发表于 2021-09-14 09:00:00
0 0
星夜

跟着大佬输出,感觉能量满满

发表于 2021-09-13 12:50:00
0 0
Ciszewski

技多不压身

发表于 2021-09-11 20:20:00
0 0
梦寻

快慢指针,最开始我还试过标记法(愚蠢)

发表于 2021-02-02 17:54:20
0 0
回忆7665

此题非常适合快慢指针

发表于 2021-02-02 11:14:49
0 0
假期2478

两个指针,看看是否有重叠

发表于 2021-01-14 12:28:33
0 0