链表带环问题求解？是否带环，环的入口点，环长度

(1)链表是否有环?

设置两个指针(fast, slow)，初始值都指向头，slow每次前进一步，fast每次前进二步，如果链表存在环，则fast必定先进入环，而slow后进入环，两个指针必定相遇，设碰撞点为p。(当然，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;
    }

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

    return true;
}

(2)找到环的入口点？

定理：slow和fast相遇点为p，让slow从head开始，fast从p开始，每次往后各走一步，直到slow和fast再次相遇，则相遇点即为环的入口。

当快慢指针第一次相遇的时候，从相遇那个节点到环入口的节点和链表头结点到环入口的节点的距离相等，所以此时让一个指针从链头开始跑，一个指针从相遇的节点开始跑，那么相遇时，这个相遇节点便是环的入口节点。

那么会有一个问题：

这俩个距离为什么会相等，我们来证明一下。

当慢指针和快指针相遇的时候，快指针必然在环中转了n圈

所以有：2s = s + nr ；  s为慢指针走过的距离，r 为环的长度

可以得出  s = nr

假设环入口到相遇节点的距离为x，链头节点到环入口的距离为a，链表长度为L

所以有 x + a = s  ；由上面替换得到  x + a = nr   ==> x+ a =(n-1)r +r ==> x + a = (n-1)r +L - a 

所以有  a = (n-1)r +L - a - x；我们发现抛去转的圈数，刚好就是相遇节点到环入口的距离 == 链头节点到环入口的距离。

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

ListNode *FindLoopPort(slist *head)
{
    ListNode *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;
}

(3)如何知道环的长度？

记录下碰撞点meet，slow、fast从该点开始，再次碰撞所走过的操作数就是环的长度r。

unsigned int GetLoopLength(slist *head)
{
    ListNode*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 0;

    ListNode *meet = slow;
    slow = meet->next;
    fast = meet->next->next;
    unsigned int len = 1;
    while (slow != fast)
    {
        len ++;
        slow = slow->next;
        fast = fast->next->next;
    }

    return len;
}

(4)带环链表的长度是多少？

L=a+r。

(5)判断两个单链表是否相交？

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

比较好的方法有两个：

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

二、如果两个链表相交，那个两个链表从相交点到链表结束都是相同的节点，我们可以先遍历一个链表，直到尾部，再遍历另外一个链表，如果也可以走到同样的结尾点，则两个链表相交。这时我们记下两个链表length，再遍历一次，长链表节点先出发前进(lengthMax-lengthMin)步，之后两个链表同时前进，每次一步，相遇的第一点即为两个链表相交的第一个点。

当前文章：链表带环问题求解？是否带环，环的入口点，环长度
标题路径：http://6mz.cn/article/peeiph.html