试题
考点

数据结构-链表-单向链表

面5笔5

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

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

如果只用一个指针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);
}





评论

pyyyyy

2023-07-13 22:00:00

0 0

CandyPilot

2021-09-09 16:05:00

0 0

假期

2021-03-01 23:43:18

0 0

ZZZ29

2021-03-01 10:26:12

0 0

木木9527

2020-10-29 15:06:34

0 0

落地98K

2018-10-13 14:44:52

0 0

途安米

2020-10-29 12:01:59

1 0

加载更多