判断链表是否有环

Check whether the linked list is either NULL-teminated or not. If there is a cycle, find start node of the loop and find the length of the loop.

楼主知道答案吗？怎么感觉出了记录所有经过的节点也没什么好方法了。。。

回复 2# 剑魔独孤求败


    那样空间复杂度太高了。。  其实可以用2个指针啊。   就像2个人赛跑，起点一样，如果是跑圈，跑得快的那个人肯定会再次遇到跑得慢的啊。 就利用这个原理

回复 2# 剑魔独孤求败


    代码如下：

1. typedef struct{
   
2.    NODE *start;//start node of the
   
3.      int len;//the length of the loop.
   
4. }loop; //return this for result
   
5. 
   
6. NODE *findstart(NODE *head, NODE *fast){
   
7.     if(fast==NULL||head==NULL)   return NULL;
   
8.            NODE *start=(NODE *)malloc(sizeof(NODE));
   
9.            if(start==NULL)  exit(0);
   
10.            start=head;
    
11.         while(start!=fast){
    
12.            start=start->next;
    
13.            fast=fast->next;
    
14.            if(fast==NULL) return NULL;
    
15.         }
    
16. 
    
17.         return fast;
    
18. 
    
19. }
    
20. 
    
21. int findlen(NODE *start){
    
22.     NODE *temp=(NODE *)malloc(sizeof(NODE));
    
23.            if(temp==NULL)  exit(0);
    
24.            temp=start;
    
25.            int len=0;
    
26.           while(1){
    
27.             start=start->next;
    
28.             len++;
    
29.             if(start==temp||start==NULL)  break;
    
30.            }
    
31.            return len;
    
32. 
    
33. }
    
34. 
    
35. 
    
36. loop *checkCircle(NODE *head){
    
37.     if(head==NULL)  return NULL;
    
38.             NODE *slow=(NODE *)malloc(sizeof(NODE));
    
39.             if(slow==NULL) exit(0);
    
40.            NODE *fast=(NODE *)malloc(sizeof(NODE));
    
41.            if(fast==NULL) exit(0);
    
42.            slow=head;
    
43.            fast=head;
    
44.            loop *lo=(loop *)malloc(sizeof(loop));
    
45.     if(lo==NULL)  exit(0);
    
46.            while(fast!=NULL&&fast->next!=NULL){
    
47.                fast= fast->next->next;
    
48.                slow=slow->next;
    
49.                if(fast==slow){
    
50.              
    
51.                            lo->start=findstart(head,fast);
    
52.                                    lo->len=findlen(lo->start);
    
53.                                    fast=NULL;
    
54.                                    free(fast);
    
55.                                    slow=NULL;
    
56.                                    free(slow);
    
57.                                   return lo;
    
58.     }
    
59.        
    
60.         }
    
61.              lo->start=NULL;
    
62.              lo->len=0;
    
63.              fast=NULL;
    
64.             free(fast);
    
65.             slow=NULL;
    
66.             free(slow);
    
67.             return lo;
    
68. }
    

复制代码

不就是一个指针走两步, 一个指针走一步, 判断未来相交的可能性.
证明就用相对论来证吧, wa ka ka ....

回复 5# wwwyhx


    版主大人高见! 但是然后还要返回环的起点，这时候需要让一个指针从链表头出发，让另外一个指针从他俩相遇的点出发，2个指针再次相遇的点就是起点。

回复 1# lhy1987


google
Floyd's cycle-finding algorithm

链表检测cycle的经典算法。每个码工必须知道的吧。哈哈。。。

一个指针每次两步 一个每次一步 check最后是否相遇
相当经典的一道算法题~

这题貌似还有一种算法，reverse整个linked list,看是否会会回到起点

- 發送自我的 iPhone 大板凳應用