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

麻麦皮

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语句
直接退出函数
可以调试一下试试

跳转到最佳答案楼层

赚小钱

不懂你的比较步数是什么意思

1. 
   
2. struct Node {
   
3.     int value;
   
4.     struct Node *next;
   
5. };
   
6. 
   
7. 
   
8. struct LinkedList {
   
9.     struct Node *head;
   
10. };
    
11. 
    
12. 
    
13. int linked_list_is_circular(struct LinkedList* list) {
    
14.     if (list == NULL || list->head == NULL || list->head->next == NULL) {
    
15.         return 0;
    
16.     }
    
17.     struct Node* slow = list->head;
    
18.     struct Node* fast = list->head->next;
    
19.     while (fast != NULL && fast->next != NULL) {
    
20.         if (slow == fast) {
    
21.             return 1;
    
22.         }
    
23.         slow = slow->next;
    
24.         fast = fast->next->next;
    
25.     }
    
26.     return 0;
    
27. }
    

复制代码

麻麦皮

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

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

赚小钱

麻麦皮 发表于 2020-5-26 19:38
你这是快慢指针，小甲鱼线性表14讲了一个方法就是比较步数

不知道，没看过。 我去找找看一下吧。

Mr、渐行渐远

内层循环目的是让cur2追上cur1，当cur2追上cur1的时候，如果有环，就直接退出函数了，如果没环，就会跳出里面的循环，接着往后走

1. bool isCircle(LinkList L)
   
2. {
   
3.         LinkList p, q;
   
4.         p = L->next;
   
5.         int step_p=0, step_q;
   
6.         while(p)
   
7.         {
   
8.                 step_q = 0;
   
9.                 q = L->next;
   
10.                 p = p->next;
    
11.                 step_p ++;
    
12.                 while(q!=p)
    
13.                 {
    
14.                         q = q->next;
    
15.                         step_q ++;
    
16.                 }
    
17.                 if(step_p!=step_q)
    
18.                 {
    
19.                         return true;
    
20.                 }
    
21.         }
    
22.         return false;
    
23. }

复制代码

麻麦皮

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

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

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

Mr、渐行渐远

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

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

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

麻麦皮

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

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