算法-链表算法-链表算法
面5笔5单链表中是否有环,写出代码
思路
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);
}