归档时间:四月, 2013

在链表寻找环

四 14 2013 由 创建在标签 开发

编程之美:两个链表相交问题

编程之美中有一篇获取链表中是否有环的问题,作者提出来两种解法,一种是将B链表尾部与A链表头相连,然后以此为A为起点遍历,要是遍历到A节点,则两个链表指向同一个节点;

另一个解法是直接遍历到链表尾部,比较最后一个节点是否为同一个节点,相同即两链表相交,不同则链表无焦点。

 

判断一个链表中是否形成环

上面的解法一可以扩展一下,如果有一个链表,开始我们不知道是否有环,如何判断是否形成了环?

解法一:

假设有N个节点,我们可以先遍历N次,然后以此节点作为参考,继续遍历,要是中途有相同的节点,则有环;若无环,则不会循环比。

解法二:

上面一种解法有一个很严重的漏洞,就是如果我的节点个数未知,那如何比较呢?我们不清楚究竟从何处开始形成环,也没有办法选择参考。

此时可以参考图深度(广度)遍历算法中使用的方法,增加一个标志位来记录已经访问过的节点,只要每次比较和记录节点的颜色就可以判断是否已经成环,如果遍历过程中有已经访问过的节点,则说明已经成环;如果遍历结束,则未成环。

这种算法通过增加空间来标识访问的节点,需要增加的存储空间为O(N);

解法三:

如果我们将现在的链表表头同时赋给两个不同的指针,同时遍历链表,但是两个以不同的步长遍历,一个指针依次遍历每个节点,而另一个节点每次以2为步长遍历,即每次遍历时间隔一个节点。通过判断两个指针是否相同或者是否到达尾部来确定是否成环。

这个类似于两个人跑步,一个人是另一个人速度的两倍,当围着环形操场跑时(即链表有环),则会出现一种情况,快的追赶跑得慢的人,每次两个人缩短1的距离,这样一旦慢的进入环中,最多只要慢的跑半个环就可以判断是否存在环了。

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);

}

判断环的交点

一个个去遍历判断效率会很慢,可以使用一个定理:

碰撞点p到连接点的距离=头指针到连接点的距离

因此,分别从碰撞点、头指针开始走,相遇的那个点就是连接点。

证明:
辅助理解图
假设单链表的总长度为L,头结点到环入口的距离为a,环入口到快慢指针相遇的结点距离为x,环的长度为r,慢指针总共走了s步,则快指针走了2s步。另外,快指针要追上慢指针的话快指针至少要在环里面转了一圈多(假设转了n圈加x的距离),得到以下关系:

r = L – a + 1;

s = a + x;

2s = a + nr + x;

则:a + x = nr;

a = nr - x;

由上式可知:若在头结点和相遇结点分别设一指针,同步(单步)前进,则最后一定相遇在环入口结点。

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;
}

判断环的长度

当发生碰撞后,再次碰撞所走过的操作数就是环的长度s。

参考

1、http://blog.csdn.net/liuxialong/article/details/6555850

2、编程之美

无评论