c++ - 列表循环检测

Question

关闭。这个问题需要debugging details .它目前不接受答案。












想改善这个问题吗？更新问题，使其成为 on-topic对于堆栈溢出。

1年前关闭。




Improve this 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

循环中的第一个节点是一个有 2 个其他节点指向的节点:



可以做的是迭代列表，保留所有节点地址并检查地址何时已被记录。这个地址是循环开始节点。

示例代码:

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