随笔 - 89  文章 - 118  trackbacks - 0
<2010年9月>
2930311234
567891011
12131415161718
19202122232425
262728293012
3456789

留言簿(16)

随笔分类(56)

随笔档案(89)

文章分类

推荐博客

搜索

  •  

最新随笔

最新评论

阅读排行榜

有一个单链表,其中可能有一个环,也就是某个节点的next指向的是链表中在它之前的节点,这样在链表的尾部形成一环。

问题:

1、如何判断一个链表是不是这类链表?
2、如果链表为存在环,如何找到环的入口点?

解答:

一、判断链表是否存在环,办法为:

设置两个指针(fast, slow),初始值都指向头,slow每次前进一步,fast每次前进二步,如果链表存在环,则fast必定先进入环,而slow后进入环,两个指针必定相遇。(当然,fast先行头到尾部为NULL,则为无环链表)程序如下:

bool IsExitsLoop(slist *head)
{
    slist
*slow = head*fast = head;

    while ( fast && fast->next ) 
    {
        slow 
= slow->next;
        fast 
= fast->next->next;
       
if ( slow == fast ) break;
    }

    return !(fast == NULL || fast->next == NULL);
}

二、找到环的入口点

当fast若与slow相遇时,slow肯定没有走遍历完链表,而fast已经在环内循环了n圈(1<=n)。假设slow走了s步,则fast走了2s步(fast步数还等于s 加上在环上多转的n圈),设环长为r,则:

2s = s + nr
s= nr

设整个链表长L,入口环与相遇点距离为x,起点到环入口点的距离为a。
a + x = nr
a + x = (n – 1)r +r = (n-1)r + L - a
a = (n-1)r + (L – a – x)

(L – a – x)为相遇点到环入口点的距离,由此可知,从链表头到环入口点等于(n-1)循环内环+相遇点到环入口点,于是我们从链表头、与相遇点分别设一个指针,每次各走一步,两个指针必定相遇,且相遇第一点为环入口点。程序描述如下:

slist* FindLoopPort(slist *head)
{
    slist
*slow = head, *fast = head;

    while ( fast && fast->next ) 
    {
        slow 
= slow->next;
        fast 
= fast->next->next;
       
if ( slow == fast ) break;
    }

    if (fast == NULL || fast->next == NULL)
   
    return NULL;

    slow 
= head;
    while (slow != fast)
    {
         slow 
= slow->next;
         fast 
= fast->next;
    }

    return slow;
}


扩展问题:

判断两个单链表是否相交,如果相交,给出相交的第一个点(两个链表都不存在环)。

比较好的方法有两个:

一、将其中一个链表首尾相连,检测另外一个链表是否存在环,如果存在,则两个链表相交,而检测出来的依赖环入口即为相交的第一个点。

二、如果两个链表相交,那个两个链表从相交点到链表结束都是相同的节点,我们可以先遍历一个链表,直到尾部,再遍历另外一个链表,如果也可以走到同样的结尾点,则两个链表相交。

这时我们记下两个链表length,再遍历一次,长链表节点先出发前进(lengthMax-lengthMin)步,之后两个链表同时前进,每次一步,相遇的第一点即为两个链表相交的第一个点。



posted on 2008-04-17 10:21 胡满超 阅读(32516) 评论(23)  编辑 收藏 引用

FeedBack:
# re: 判断单链表是否存在环,判断两个链表是否相交问题详解 2008-04-17 11:03 大海
写得太好了,受教育了  回复  更多评论
  
# re: 判断单链表是否存在环,判断两个链表是否相交问题详解[未登录] 2008-04-17 11:28 steven
太强了  回复  更多评论
  
# re: 判断单链表是否存在环,判断两个链表是否相交问题详解[未登录] 2008-04-17 12:25 AAAA
很好!  回复  更多评论
  
# re: 判断单链表是否存在环,判断两个链表是否相交问题详解 2008-04-17 13:36 seraph.cxl
强人,顶  回复  更多评论
  
# re: 判断单链表是否存在环,判断两个链表是否相交问题详解 2008-04-17 13:41 FongLuo
好解法!  回复  更多评论
  
# re: 判断单链表是否存在环,判断两个链表是否相交问题详解 2008-05-22 14:06 jie
不错,记下了  回复  更多评论
  
# re: 判断单链表是否存在环,判断两个链表是否相交问题详解 2009-04-18 17:41 ll
slow == head 时没有做判断  回复  更多评论
  
# re: 判断单链表是否存在环,判断两个链表是否相交问题详解[未登录] 2010-06-11 15:45 fish
slow-1 ,fast-2 请问他们一定会相遇吗,会不会每次都错过呢?  回复  更多评论
  
# re: 判断单链表是否存在环,判断两个链表是否相交问题详解[未登录] 2010-11-10 00:08 bill
@fish
当然不会啊。。追及问题啊,fast每次都比slow多走一步,他们的距离每次都缩小1,一段时间后就会追上了  回复  更多评论
  
# re: 判断单链表是否存在环,判断两个链表是否相交问题详解 2010-11-10 21:16 nkconst
@bill
2s = s + nr
s= nr

设整个链表长L,入口环与相遇点距离为x,起点到环入口点的距离为a。
a + x = nr
a + x = (n – 1)r +r = (n-1)r + L - a
a = (n-1)r + (L – a – x)
====
其实得到了a + x = nr 后面就不用再多解释了,也就是找到了一个距离,这个距离是环长的整数倍,那么只要将两个指针放到这个距离两边,跑一下就可以了。

  回复  更多评论
  
# re: 判断单链表是否存在环,判断两个链表是否相交问题详解[未登录] 2012-02-20 12:00 初学者
判断两个单链表是否相交,如果相交,给出相交的第一个点(两个链表都不存在环)。

===========================
方法3 :
记链表1的节点数为 count1
记链表2的节点数为 count2
取两个链表的节点数较小的一个链表(假设是count2), 最长的公共子节点集不会大于count2 , 移动链表1 指针(count1 - count2)次 , 与此同时链表2 从head 处开始一起移动指针,做判断, 如果移动的过程中指针相等,找到相交点, 返回, 否则,直到各自终点, 无相交点

  回复  更多评论
  
# re: 判断单链表是否存在环,判断两个链表是否相交问题详解[未登录] 2012-02-21 11:33 初学者
我认为 你的循环条件还可以再简单一点

while ( fast && fast->next ) =〉while ( fast )

因为一旦有环存在 , fast->next 永远为1
如果无环, fast = fast->_next->_next; 也可以保证fast 为0


请问我的分析正确吗   回复  更多评论
  
# re: 判断单链表是否存在环,判断两个链表是否相交问题详解 2012-02-21 17:43 胡满超
@初学者
好像不行,如果链表只有一个节点,或者无环遍历fast到最后一个节点的时候,走到这句

fast = fast->next->next;

程序会出现非法指针的访问  回复  更多评论
  
# re: 判断单链表是否存在环,判断两个链表是否相交问题详解[未登录] 2012-02-23 15:41 初学者
@胡满超
谢谢指教, 你说的对  回复  更多评论
  
# re: 判断单链表是否存在环,判断两个链表是否相交问题详解 2012-09-26 16:51 frankxie
不错,学习了。  回复  更多评论
  
# re: 判断单链表是否存在环,判断两个链表是否相交问题详解 2012-09-26 16:51 frankxie
不错,学习了  回复  更多评论
  
# re: 判断单链表是否存在环,判断两个链表是否相交问题详解 2012-09-26 16:53 frankxie
@胡满超
很好。。  回复  更多评论
  
# re: 判断单链表是否存在环,判断两个链表是否相交问题详解 2012-11-11 23:12 科匠
“当fast若与slow相遇时,slow肯定没有走遍历完链表,而fast已经在环内循环了n圈(1<=n) 。”

有问题?slow有可能走完一圈了。
你用带四个节点的环模拟一下。slow有可能遍历完的。

  回复  更多评论
  
# re: 判断单链表是否存在环,判断两个链表是否相交问题详解 2012-11-12 09:01 胡满超
您是对的,您指的是四个节点,且最后一个节点向第一个节点,就出现了您说的情况@科匠

  回复  更多评论
  
# re: 判断单链表是否存在环,判断两个链表是否相交问题详解 2014-03-12 22:13 xiximydream
可以理解fast走2步,slow走1步,因为走k次后,他们的距离为2*k-k=k可以为任意整数,我想问fast走3步可否,是否能更快发现环  回复  更多评论
  
# re: 判断单链表是否存在环,判断两个链表是否相交问题详解 2015-01-09 04:59 gqqnbig
当fast若与slow相遇时,slow肯定没有走遍历完链表@科匠

那有没有可能slow已经走了多于一圈了呢?  回复  更多评论
  
# re: 判断单链表是否存在环,判断两个链表是否相交问题详解 2015-03-22 16:11 lookdown
n只可能是1  回复  更多评论
  

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理