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的起始地址赋给头指针headt1.next = &t2;//将节点t2的起始地址赋给t1节点中的nextt2.next = &t3;//将节点t3的起始地址赋给t2节点中的nextt3.next = &t4;//将节点t4的起始地址赋给t3节点中的nextt4.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:2C:\Users\lenovo\source\repos\Project1\x64\Debug\Project1.exe (进程 18944)已退出，代码为 0。
要在调试停止时自动关闭控制台，请启用“工具”->“选项”->“调试”->“调试停止时自动关闭控制台”。
按任意键关闭此窗口. . .