Chinaunix首页 | 论坛 | 博客
  • 博客访问: 8005656
  • 博文数量: 159
  • 博客积分: 10424
  • 博客等级: 少将
  • 技术积分: 14615
  • 用 户 组: 普通用户
  • 注册时间: 2010-07-14 12:45
个人简介

啦啦啦~~~

文章分类
文章存档

2015年(5)

2014年(1)

2013年(5)

2012年(10)

2011年(116)

2010年(22)

分类: C/C++

2011-08-15 21:02:31

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

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

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


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

下面上代码
  1. struct list_node {
  2.     struct list_node *next;
  3.     void *data;
  4. };

  5. #define FALSE 0
  6. #define TRUE 1
  7. typedef unsigned char bool;

  8. bool is_list_exist_loop(struct list_node *head)
  9. {
  10. /* 
  11. 快指针步进长度,之前我认为可以为其它值,但是从Bean_lee的回复中知道,不能为超过循环节点个数的值。
  12. 当超过循环节点个数时,而慢结点还未步入这个循环时,快节点会一直在循环中步进直至慢节点也步入这个循环。
  13.  */
  14. #define FAST_POINT_STEP        2

  15.     if (!head) return FALSE;

  16.     struct list_node *fast, *slow;
  17.     unsigned int i;
    
     /* 快慢指针都处于同一起跑线,即头指针位置 */
  1.     fast = slow = head;

  2.     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.     return FALSE;
  4. }

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







阅读(10122) | 评论(15) | 转发(8) |
给主人留下些什么吧!~~

Bean_lee2011-08-16 21:20:41

GFree_Wind: 个人觉得,只要不大于链表本身的长度,就可以吧。如果大于等于链表本身长度,就等于之前说的那种两重循环了。

你觉得呢?.....
考虑这种情况,环内节点为N,你选的快的步长为k*N+1,那么你的快指针永远遇不到慢指针,因为,在环内,无论快指针和慢指针之间的差距是一致的。

换言之,如果环内节点有4个,如果你快指针的步长为5,那么,很有可能你的两个指针永不相遇。

兄弟详之。

GFree_Wind2011-08-16 21:09:44

Bean_lee: #define FAST_POINT_STEP        2
这个好像不是随便大于等于2的值都可以的。.....
个人觉得,只要不大于链表本身的长度,就可以吧。如果大于等于链表本身长度,就等于之前说的那种两重循环了。

你觉得呢?

Bean_lee2011-08-16 21:05:36

#define FAST_POINT_STEP        2
这个好像不是随便大于等于2的值都可以的。

GFree_Wind2011-08-16 18:00:41

sunxphere: 慢指针步进应该是 slow = slow->nex; 吧.....
是的。笔误,多谢指出,已更正

sunxphere2011-08-16 16:15:38

慢指针步进应该是 slow = slow->nex; 吧