Chinaunix首页 | 论坛 | 博客
  • 博客访问: 6563328
  • 博文数量: 159
  • 博客积分: 10424
  • 博客等级: 少将
  • 技术积分: 14594
  • 用 户 组: 普通用户
  • 注册时间: 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. }

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







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

GFree_Wind2011-09-07 16:27:57

yadsun: 这个似乎有问题吧,
如果慢指针恰好每次都落在快指针的步长区间之内,即快指针的步进每次都恰好跨过了慢指针,这种情况也没办法判断吧.....
落在步长区间,没有关系。当快指针步进的时候,每次都会检查是否遇到了慢指针。如果遇到了,那么就是有环。

yadsun2011-09-07 15:20:13

这个似乎有问题吧,
如果慢指针恰好每次都落在快指针的步长区间之内,即快指针的步进每次都恰好跨过了慢指针,这种情况也没办法判断吧

GFree_Wind2011-08-25 22:20:13

warthlanw: 呵呵,确实效率有比较大的问题。我也是就当前代码而论,读代码,解代码。其实是你的这份代码让我想到的。.....
我也是你一说,才想到的。之前也认为Bean说得对

warthlanw2011-08-25 18:23:50

GFree_Wind: 你考虑这种情况,当慢结点还未进入循环时,快节点已经开始在循环中步进。这时,是检测不出循环的。

直到慢结点步入循环以后,才能检测出。

所以虽然仍然可以检.....
呵呵,确实效率有比较大的问题。我也是就当前代码而论,读代码,解代码。其实是你的这份代码让我想到的。

GFree_Wind2011-08-25 18:01:58

warthlanw: 关于Bean_Lee兄的关于步长的结论在这个程序里面似乎并不适用,因为在这段代码里面快指针并不是一次性走完一个步长,而是通过循环,每找一个next就测试下看看是否.....
你考虑这种情况,当慢结点还未进入循环时,快节点已经开始在循环中步进。这时,是检测不出循环的。

直到慢结点步入循环以后,才能检测出。

所以虽然仍然可以检测出循环,但是效率可能会有些问题。

不过可能他没想到这种情况。我也是刚刚想到的呵。

评论热议
请登录后评论。

登录 注册