试题
考点

算法-链表算法-链表算法

面5笔5

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

前往“校招VIP”小程序,刷题更快
最新校招难题刷题,快来进刷题群吧
解答

思路

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);
}

评论

望岳

2021-12-15 21:00:00

0 0

星夜

2021-09-13 12:50:00

0 0

Ciszewski

2021-09-11 20:20:00

0 0

回忆7665

2021-02-02 11:14:49

0 0

假期2478

2021-01-14 12:28:33

0 0

加载更多