随笔 - 88  文章 - 118  trackbacks - 0
<2008年4月>
303112345
6789101112
13141516171819
20212223242526
27282930123
45678910

留言簿(15)

随笔分类(54)

随笔档案(88)

文章分类

推荐博客

搜索

  •  

最新随笔

最新评论

阅读排行榜

04 2008 档案
判断单链表是否存在环,判断两个链表是否相交问题详解      摘要: 有一个单链表,其中可能有一个环,也就是某个节点的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;  阅读全文
posted @ 2008-04-17 10:21 胡满超 阅读(32146) | 评论 (23)  编辑