寻找链表中环的位置

参考https://blog.csdn.net/zwx900102/article/details/122293540
链表结构定义

#include <iostream>
#include <unordered_set>

using namespace std;

typedef struct ListNode
{
    int data;
    ListNode* next;
}*List;

链表的尾插法和遍历函数实现

//尾插法 
void InsertTail(List& L, int data)
{
    ListNode* p = L;                    //头结点
    ListNode* n = new ListNode;
    n->data = data;
    n->next = NULL;

    if (p->next != NULL)
    {
        while (p->next)
        {
            p = p->next;
        }
    }
    p->next = n;
}
//遍历
void TraverseList(List L)
{
    ListNode* p = L->next;
    while (p)
    {
        cout << p->data << " ";
        p = p->next;
    }
    cout << endl;
}

使用哈希表判断链表是否有环，并找到环的入口点

bool IsCycle_hash(List L)
{
    unordered_set<ListNode*> h;

    ListNode* p = L->next;
    while (p)
    {

        if (h.find(p) != h.end())           //如果再哈希表中找到了当前结点
        {
            cout << "入口点：" << p->data << endl;
            return true;
        }

        h.insert(p);
        p = p->next;
    }
    return false;
}

使用快慢指针判断链表是否有环并寻找环的位置

bool IsCycle(List L)
{
    ListNode* slow = L;         //慢指针
    ListNode* fast = L->next->next;         //快指针

    while (fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;

        if (slow == fast)
        {
            return true;
        }
    }
    return false;
}

//查找环的入口位置
int FindCycle(List L)
{
    ListNode* slow = L;                         //慢指针
    ListNode* fast = L;                         //快指针

    while (fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;

        if (slow == fast)                       //快慢指针相遇则证明有环
        {
            slow = L;                           //慢指针重新指向链表头指针
            while (slow != fast)                //从相遇点和头指针一起后移，再次相遇的点则为入口点
            {
                slow = slow->next;
                fast = fast->next;
            }
            return slow->data;
        }
    }

    return 0;                                   //未找到环
}

main函数

int main(int argc, char** argv)
{
    List l = new ListNode;      //头结点
    l->next = NULL;

    InsertTail(l, 1);
    InsertTail(l, 2);
    InsertTail(l, 3);
    InsertTail(l, 4);
    InsertTail(l, 5);

    TraverseList(l);

    //构成一个环
    ListNode* p = l;
    while (p->next)
    {
        p = p->next;                    //找到最后一个结点
    }
    p->next = l->next->next;            //最后一个结点的next域指向第二个结点，构成一个环
    //p->next = p;                      //最后一个结点的next域指向自身，构成一个环

    cout << "入口点：" << p->next->data << endl;
    cout << "是否有环：" << IsCycle(l) << endl;
    cout << "入口点：" << FindCycle(l) << endl;

    cout << "*********************使用hash_set求解**************" << endl;
    cout << "是否有环：" << IsCycle_hash(l) << endl;

    return 0;
}