怎样才能检测到链表中循环

水深无声 2022-09-18 01:44 178阅读 0赞

《C专家编程》附录A.2

![SouthEast][]

~~~~~~~~~~~~~~~~~~~~~~割了？~~~~~~~~~~~~~~~~~~

[http://blog.chinaunix.net/uid-23629988-id-2191643.html][http_blog.chinaunix.net_uid-23629988-id-2191643.html]

[算法实现：使用快慢指针，检测单链表是否存在循环][http_blog.chinaunix.net_uid-23629988-id-2191643.html]*2011-08-15 21:02:31*

分类： C/C++

本文的copyleft归gfree.wind@gmail.com所有，使用GPL发布，可以自由拷贝，转载。但转载请保持文档的完整性，注明原作者及原链接，严禁用于任何商业用途。  
作者：gfree.wind@gmail.com  
博客：linuxfocus.blog.chinaunix.net

今天的题目是检查单链表是否存在循环。对于初学者来说，要解决这个问题，最可能采取的方法就是使用两个循环。当外层循环步进一个节点时，内层循环就遍历外层循环节点之后的所有节点，然后比较内外循环的两个节点。若有节点地址相等，则表明该单链表有循环，反之则不存在循环。 这种方法无疑效率比较低。

今天给大家介绍一个经典的方法，通过快慢指针来检查单链表是否存在循环。其思路很简单，大家可以想一下上体育课长跑的情景。当同学们绕着操场跑步的时候，速度快的同学会遥遥领先，最后甚至会超越其它同学一圈乃至n圈——这是绕圈跑。那么如果不是绕圈跑呢？速度快的同学则会一直领先直到终点，不会再次碰到后面的速度慢同学——不考虑地球是圆的这种情况O(∩\_∩)O哈！

快慢指针的设计思想也是这样。快指针每次步进多个节点——这个视情况而定，慢指针每次只步进一个节点。那么如果该链表存在循环的话，快指针一定会再次碰到慢指针，反之则不存在循环。

下面上代码

1.  1.  struct list\_node \{   
        
    2.      struct list\_node \*next;  
        
    3.      void \*data;  
        
    4.  \};  
        
    5.    
        
    6.  \#define FALSE 0  
        
    7.  \#define TRUE  1  
        
    8.  typedef unsigned char bool;  
        
    9.    
        
    10. bool is\_list\_exist\_loop(struct list\_node  \*head)  
        
    11. \{   
        
    12. /\* 
    13. 快指针步进长度，之前我认为可以为其它值，但是从Bean\_lee的回复中知道，不能为超过循环节点个数的值。
    14. 当超过循环节点个数时，而慢结点还未步入这个循环时，快节点会一直在循环中步进直至慢节点也步入这个循环。
    15. \*/
    16. \#define FAST\_POINT\_STEP        2  
        
    17.   
        
    18.     if (!head) returnFALSE;  
        
    19.   
        
    20.     struct list\_node \*fast,\*slow;  
        
    21.     unsigned int i;  
        
    
        
    
         /\* 快慢指针都处于同一起跑线，即头指针位置 \*/
    
    1.      fast = slow = head;  
        
    2.    
        
    3.      while (fast)\{   
        
    
             /\* 快指针步进 \*/
    
    1.          for (i= 0; i < FAST\_POINT\_STEP; \+\+i) \{   
        
    2.              fast = fast\->next;
    3.              if (fast== slow)\{   
        
    4.                  /\* 又碰到了慢指针，循环存在 \*/
    5.                  return TRUE;  
        
    6.              \}  
        
    7.              else if(!fast)\{   
        
    8.                  /\* 快指针跑到头了，循环不存在 \*/
    9.                  return FALSE;  
        
    10.             \}  
        
    11.         \}  
        
    
       
    
             /\* 慢指针步进 \*/
    
    1.          slow = slow->next;  
        
    2.      \}  
        
    3.    
        
    4.      return FALSE;  
        
    5.  \}

仍然是抛砖引玉，大家还有什么经典的方法来解决这个问题呢？

[SouthEast]: /images/20220828/e88f9bd8ca4b4721b7cf903ce2de32a6.png
[http_blog.chinaunix.net_uid-23629988-id-2191643.html]: http://blog.chinaunix.net/uid-23629988-id-2191643.html