參考https://blog.csdn.net/zwx900102/article/details/122293540
鏈表結(jié)構(gòu)定義

#include <iostream>
#include <unordered_set>

using namespace std;

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

鏈表的尾插法和遍歷函數(shù)實現(xiàn)

//尾插法 
void InsertTail(List& L, int data)
{
    ListNode* p = L;                    //頭結(jié)點
    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;
}

使用哈希表判斷鏈表是否有環(huán)，并找到環(huán)的入口點

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

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

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

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

使用快慢指針判斷鏈表是否有環(huán)并尋找環(huán)的位置

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

//查找環(huán)的入口位置
int FindCycle(List L)
{
    ListNode* slow = L;                         //慢指針
    ListNode* fast = L;                         //快指針

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

        if (slow == fast)                       //快慢指針相遇則證明有環(huán)
        {
            slow = L;                           //慢指針重新指向鏈表頭指針
            while (slow != fast)                //從相遇點和頭指針一起后移，再次相遇的點則為入口點
            {
                slow = slow->next;
                fast = fast->next;
            }
            return slow->data;
        }
    }

    return 0;                                   //未找到環(huán)
}

main函數(shù)

int main(int argc, char** argv)
{
    List l = new ListNode;      //頭結(jié)點
    l->next = NULL;

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

    TraverseList(l);

    //構(gòu)成一個環(huán)
    ListNode* p = l;
    while (p->next)
    {
        p = p->next;                    //找到最后一個結(jié)點
    }
    p->next = l->next->next;            //最后一個結(jié)點的next域指向第二個結(jié)點，構(gòu)成一個環(huán)
    //p->next = p;                      //最后一個結(jié)點的next域指向自身，構(gòu)成一個環(huán)

    cout << "入口點：" << p->next->data << endl;
    cout << "是否有環(huán)：" << IsCycle(l) << endl;
    cout << "入口點：" << FindCycle(l) << endl;

    cout << "*********************使用hash_set求解**************" << endl;
    cout << "是否有環(huán)：" << IsCycle_hash(l) << endl;

    return 0;
}