数据结构-链表-单向链表
面5笔5判断单链表中是否有环,写出代码
如果只用一个指针next的话 ,是不能知道到底有环造成一直循环还是链表长度很长造成的,而且循环了的话,程序没有终结态。
所以只能考虑两个指针low和fast,slow一次走一步,fast一次走两步。
如果存在环的话,当slow进入环后,fast每次追赶slow一步,所以一定会在slow一圈之内赶上。即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);
}