今天看到一个关于链表的数据结构题，就是说一个怎样快速判断一个单向链表中是否存在环？

设置两个指针，初始值都指向头，一个快一个慢，看是否相遇

一个人旅行 发表于 2013-12-10 22:09
设置两个指针，初始值都指向头，一个快一个慢，看是否相遇

哦，谢谢，明白了！

一个人旅行 发表于 2013-12-10 22:09
设置两个指针，初始值都指向头，一个快一个慢，看是否相遇

哦，谢谢，明白了！

1. /*  链表的头指针为h  */
   
2. if((NULL == h) || (NULL == h->next))
   
3. /* 头指针为空或者链表中只有一个节点，则无环，退出 */
   
4. {
   
5.               return 0;
   
6. }         
   
7. 
   
8. p = q = h; /* 设p和 q 指针， 均指向头结点 */
   
9. while(1)
   
10. {
    
11.     p = p->next;
    
12.     q = (q->next)->next；
    
13.     if((NULL == p) || (NULL == q))
    
14.     {
    
15.         printf(“No Ringn”); /* 链表中无环， 退出 */
    
16.         return 0;
    
17. }
    
18.     if(p == q) /* 链表中有环 */
    
19.     {
    
20.        printf(“Ring occurred\n”);
    
21.        return 1;
    
22. }
    
23. }

复制代码