解答
思路
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);
}
大佬,能转载下吗?
我想咨询下,如果是做产品经理,考研可以考哪些相关专业
跟着大佬输出,感觉能量满满
技多不压身
快慢指针,最开始我还试过标记法(愚蠢)
此题非常适合快慢指针
两个指针,看看是否有重叠