1. 题目 

2. 思路分析：

与环形链表1一样，我们需要定义慢指针和快指针，确定链表是否有环，如果链表没有环的话，直接置空即可。如果链表有环，则需要向环形链表1一样，让快指针不断追赶慢指针，找到恰好追上的结点。

本题如果想找到开始入环的第一个结点，则需要用到一个结论：定义两个新指针，一个从头开始走，一个从慢指针和快指针相遇的地方开始走，两者恰好在链表开始入环的地方相遇。

以下是证明过程：

 

如图所示，设从开始到入环的距离为L，入环到两者相遇的距离为X，慢指针走的路程为L+X，快指针走的路程为L+X+N*C（C代表环的长度），因为快指针有可能在环中走了N圈，所以这段路程要加上。由于快指针的速度是慢指针的2倍，路程也是二倍，所以有等式2*(L+X)=L+X+N*C，整理得L=C*N-X，再变形得L=C*(N-1)+C-X,说明L的长度和C-X的长度相等，只不过有可能差来N圈，由而得出上面的结论。

代码的实现按照上面的结论即可。

代码实现

/**
 * Definition for singly-linked list.*/
#include<iostream>
using namespace std;

struct ListNode {
    int val;
     ListNode *next;
     ListNode(int x) : val(x), next(nullptr) {}
};

class Solution
{
public:
    ListNode* detectCycle(ListNode* head)
    {
        ListNode* slow = nullptr;
        ListNode* fast = nullptr;
        ListNode* meet = nullptr;
        ListNode* cur = nullptr;
        slow = fast = head;
        while (fast && fast->next)
        {
            slow = slow->next;
            fast = fast->next->next;
            if (slow == fast)
            {
                meet = slow;
                cur = head;
                while (meet != cur)
                {
                    meet = meet->next;
                    cur = cur->next;
                }
                return cur;
            }
        }
        return NULL;
    }
};
int main()
{
    struct ListNode* head;
    //定义结构体变量，作为节点，给节点赋值
    struct ListNode t1  { 3};//对节点t1的data和next赋值
    struct ListNode t2 { 2 };//对节点t2的data和next赋值
    struct ListNode t3 { 0 };//对节点t3的data和next赋值
    struct ListNode t4 = { 4 };//对节点t4的data和next赋值
    struct ListNode t5 = { 2 };//对节点t5的data和next赋值

    head = &t1;//将节点t1的起始地址赋给头指针head
    t1.next = &t2;//将节点t2的起始地址赋给t1节点中的next
    t2.next = &t3;//将节点t3的起始地址赋给t2节点中的next
    t3.next = &t4;//将节点t4的起始地址赋给t3节点中的next
    t4.next = &t5;
    t5.next = &t2;
    Solution test;
    ListNode*  out = test.detectCycle(head);
    if(nullptr != out)
    {
        cout << "out->val:" << out->val << endl;
    }
    else
    {
        cout << "out is nullptr" << endl;
    }
    
}

 

out->val:2

C:\Users\lenovo\source\repos\Project1\x64\Debug\Project1.exe (进程 18944)已退出，代码为 0。
要在调试停止时自动关闭控制台，请启用“工具”->“选项”->“调试”->“调试停止时自动关闭控制台”。
按任意键关闭此窗口. . .