[已解决]单链表比较步数判断有环

麻麦皮

1. int HasLoop(LinkList L)
   
2. {
   
3.         LinkList cur1 = L;
   
4.         int pos1 = 0;
   
5.         while(cur1)
   
6.         {
   
7.                 LinkList cur2 = L;
   
8.                 int pos2 = 0;
   
9.                 while(cur2)
   
10.                 {
    
11.                         if(cur2 == cur1)
    
12.                         {
    
13.                                 if(pos1 == pos2)
    
14.                                 {
    
15.                                         break;
    
16.                                 }
    
17.                                 else
    
18.                                 {
    
19.                                         printf("%d", pos2);
    
20.                                         return 1;
    
21.                                 }
    
22.                         }
    
23.                         cur2 = cur2->next;
    
24.                         pos2++;
    
25.                 }
    
26.                 cur1 = cur1->next;
    
27.                 pos1++;
    
28.         }
    
29.         return 0;
    
30. }

复制代码

cur2 = cur2->next;如果有环的话，不就是在while(cur2)里面死循环了吗

最佳答案

月排行榜 / 总排行榜

Mr、渐行渐远

2020-5-28 20:05:06

麻麦皮 发表于 2020-5-28 17:11
我看懂了你的代码，你看一下我发的代码

while(cur2)里面cur2 = cur2->next不就是无限循环无法退出了吗

这层循环的退出方式分两种情况，并不是直接while条件判断的
1.如果没有回路，外面每循环一次，里层循环最终pos1和pos2会相等，然后break跳到外层循环，
cur1会遍历走到最后一个节点，整个函数结束
2.如果有回路，外面和里面都不会因为指向NULL而停止；cur1走到原本该向前走的地方却向后走了
，而cur2总是从起点出发，这样它们再次相遇的时候cur1走的步数比cur2多，就会执行return语句
直接退出函数
可以调试一下试试

跳转到最佳答案楼层

麻麦皮

赚小钱 发表于 2020-5-26 19:20
不懂你的比较步数是什么意思

你这是快慢指针，小甲鱼线性表14讲了一个方法就是比较步数

麻麦皮

Mr、渐行渐远 发表于 2020-5-28 08:44
内层循环目的是让cur2追上cur1，当cur2追上cur1的时候，如果有环，就直接退出函数了，如果没环，就会跳出里 ...

我看懂了你的代码，你看一下我发的代码

while(cur2)里面cur2 = cur2->next不就是无限循环无法退出了吗

麻麦皮

Mr、渐行渐远 发表于 2020-5-28 20:05
这层循环的退出方式分两种情况，并不是直接while条件判断的
1.如果没有回路，外面每循环一次，里层循环 ...

懂了，我瞎了没看到break以为一直在里面循环