列表循环检测

Question

给出一个链表，返回循环开始的节点。如果没有循环，则返回null。

使用兔子和乌龟算法检测到环路后，我无法理解从起始地址到循环检测地址的相等距离​​如何导致提供了循环起始地址。

    ListNode* Solution::detectCycle(ListNode* A) {

    ListNode* p=A;
    ListNode* q=A;
    while(p!=NULL && q!=NULL && q->next!=NULL)
    {
        p=p->next;
        q=q->next->next;
        if(p==q)
        {
            p=A;
            while(p!=q)
            {
                p=p->next;
                q=q->next;
            }
            return p;
        }
    }
    return NULL;

    }

Answer 1

循环中的第一个节点是一个节点，另外两个节点指向：

可以做什么，遍历列表，保留所有节点地址，并检查何时已记录地址。此地址是循环开始节点。

示例代码：

    #include "stdio.h"
#include <iostream>
#include <vector>

struct ListNode
{
    struct ListNode* next;
};

ListNode* detectCycle(ListNode* A) {

    ListNode* p = A;
    ListNode* q = A;
    while (p != NULL && q != NULL && q->next != NULL)
    {
        p = p->next;
        q = q->next->next;
        if (p == q)
        {
            p = A;
            while (p != q)
            {
                p = p->next;
                q = q->next;
            }
            return p;
        }
    }
    return NULL;
}


template < typename T>
std::pair<bool, int > findInVector(const std::vector<T>& vecOfElements, const T& element)
{
    std::pair<bool, int > result;

    // Find given element in vector
    auto it = std::find(vecOfElements.begin(), vecOfElements.end(), element);

    if (it != vecOfElements.end())
    {
        result.second = distance(vecOfElements.begin(), it);
        result.first = true;
    }
    else
    {
        result.first = false;
        result.second = -1;
    }

    return result;
}


int main()
{
    ListNode a, b, c, d, e, f;   // a -> b -> c -> d ->e -> f -> c;

    a.next = &b;
    b.next = &c;
    c.next = &d;
    d.next = &e;
    e.next = &f;
    f.next = &c;


    ListNode* p = detectCycle(&a);

    std::cout << p;

    std::vector<ListNode*> v;

    v.push_back(&a);

    ListNode* it = a.next;

    while (findInVector(v, it).first == false)
    {
        v.push_back(it);
        it = it->next;
    }

    std::cout << " first is " << v.at(findInVector(v, it).second) << " " << &c; 
}

Answer 2

之所以有效，是因为当您进入该空间时，如果

if (p == q)
{

您确定知道自己处于循环中：

• 从该点到循环开始的距离与]相同>

• 从列表开始到循环开始的距离。

这就是为什么您可以将指针之一重置为列表的开头并以相同的速度移动它们的原因。当他们见面时，他们在周期开始时见面。

---

我写了关于此算法的blog article。查阅更多信息。