20140707电话面试（快慢指针问题）

不念不忘少年蓝@ 2022-08-24 11:41 162阅读 0赞

上次面试到了快慢指针问题，面试官问我，如何知道一个单链表或者双向链表有没有打环，我第一感觉是用循环，判断首尾指针是否相等，很明显 答案肯定是错的，后来我又说了用2层循环遍历。答案也不是面试官想知道的。后来上网搜了一下，原来是快慢指针的问题。

今天对这个问题仔细想了下。我又想到了新的问题。如果这个单链表\\双链表打环了，如何知道这个环中有多少个元素呢，快慢指针只能知道是否打环，却不能准确的算出打环的元素有多少个？

经过分析：我找到了解决方案：可以用2层循环，只不过这个循环跟我们以前用的循环不太一样：当外层循环步进一个节点时，内层循环就从Head遍历至这个节点之前的一个节点，判断内外地址有无相等。用此方法不仅知道是否打环，而且可以知道打环节点个数，

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

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

因为 p->next ！= NULL 永远都成立）

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

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

下面上代码

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. 所以为了保证能够测出循环，那么还是设置步长为2为好
15.  \*/
16. \#define FAST\_POINT\_STEP        2  
    
17.   
    
18.     if (!head) return FALSE;  
    
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.  \}

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

[13.gif]: http://blog.chinaunix.net/blog/image/editor/pb/13.gif