一、题目描述给定一个链表的头节点head返回链表开始入环的第一个节点。如果链表无环则返回null。示例输入head [3,2,0,-4], pos 1 输出返回索引为 1 的链表节点 解释链表中有一个环其尾部连接到第二个节点。 输入head [1,2], pos 0 输出返回索引为 0 的链表节点 输入head [1], pos -1 输出null二、核心思路关键思想快慢指针 数学推导这道题是 141. 环形链表 的升级版不仅要判断是否有环还要找到入环点。两阶段法阶段1快慢指针找相遇点 阶段2双指针从相遇点和头节点同时出发再次相遇点即为入环点三、代码实现方法快慢指针 数学推导 ✅/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(nullptr) {} * }; */classSolution{public:ListNode*detectCycle(ListNode*head){ListNode*slowhead;ListNode*fasthead;// 阶段1找相遇点 while(fastfast-next){slowslow-next;fastfast-next-next;if(slowfast){// 相遇// 阶段2找入环点 slowhead;while(slow!fast){slowslow-next;fastfast-next;}returnslow;// 入环点}}returnnullptr;// 无环}};复杂度分析复杂度值说明时间O(n)最多遍历两圈空间O(1) ✅只用了两个指针四、数学推导图解为什么相遇后从头节点和相遇点同时出发会相遇在入环点设L 头到入环点的距离C 环的长度相遇时快指针走了F步L C - M ┌───────┐ ┌────────────┐ │ │ │ │ ↓ │ ↓ │ head ──→ X ─────────→ 相遇点 M ↑ │ │_______________│ (环) 慢指针走的距离 L M 快指针走的距离 L kC M (k 1)快指针速度是慢指针的2倍2(L M) L kC M L M kC L kC - M (k-1)C (C - M)当k1时L C - M即从头节点走L步 从相遇点走C-M步所以从头节点和相遇点同时走 L 步会在入环点相遇五、图解全过程示例[3,2,0,-4]入环点是节点 2链表结构 3 - 2 - 0 - -4 ↑__________| 阶段1快慢指针找相遇点 初始slow3, fast3 第1步slow2, fast0 第2步slow0, fast-4 第3步slow-4, fast-4 (第二轮) 相遇相遇点-4 阶段2找入环点 slow head 3 fast 相遇点 -4 slow3, fast-4 (不相等) slow2, fast0 (不相等) slow0, fast-4 (不相等) slow-4, fast-4 (相等相遇) 返回 slow 节点2 ✓六、代码执行流程图开始 │ ▼ 快慢指针遍历 ────────────────────┐ │ │ ├── fast走到nullptr? ──是──→ return nullptr │ └── slow fast? ──是──→ 阶段2 │ slow head │ ┌────┴────┐ │ slowfast?│ └──┬────┬─┘ 是 否 │ │ ▼ │ return │ slow(入环点) │ ←──────┘七、与141题的区别题目141. 环形链表142. 环形链表 II目标判断是否有环找入环点返回true/false节点/null代码相遇即返回相遇后再找八、其他解法不推荐方法2哈希集合ListNode*detectCycle_hash(ListNode*head){unordered_setListNode*visited;while(head){if(visited.count(head))returnhead;visited.insert(head);headhead-next;}returnnullptr;}复杂度值时间O(n)空间O(n) ❌九、方法对比方法时间空间推荐度快慢指针 数学推导O(n)O(1) ✅⭐⭐⭐最优哈希集合O(n)O(n)⭐⭐ 直观但占用空间十、完整测试代码#includeiostreamusingnamespacestd;structListNode{intval;ListNode*next;ListNode(intx):val(x),next(nullptr){}};classSolution{public:ListNode*detectCycle(ListNode*head){ListNode*slowhead;ListNode*fasthead;// 阶段1找相遇点while(fastfast-next){slowslow-next;fastfast-next-next;if(slowfast){// 阶段2找入环点slowhead;while(slow!fast){slowslow-next;fastfast-next;}returnslow;}}returnnullptr;}};// 测试辅助函数创建带环链表ListNode*createCycleList(vectorintvals,intpos){if(vals.empty())returnnullptr;ListNode*headnewListNode(vals[0]);ListNode*currhead;ListNode*cycleNodenullptr;if(pos0)cycleNodehead;for(inti1;ivals.size();i){curr-nextnewListNode(vals[i]);currcurr-next;if(ipos)cycleNodecurr;}if(pos0){curr-nextcycleNode;// 形成环}returnhead;}intmain(){Solution sol;// 测试1有环入环点是索引1ListNode*head1createCycleList({3,2,0,-4},1);ListNode*node1sol.detectCycle(head1);cout入环点值: (node1?to_string(node1-val):null)endl;// 测试2有环入环点是索引0ListNode*head2createCycleList({1,2},0);ListNode*node2sol.detectCycle(head2);cout入环点值: (node2?to_string(node2-val):null)endl;// 测试3无环ListNode*head3createCycleList({1},-1);ListNode*node3sol.detectCycle(head3);cout入环点值: (node3?to_string(node3-val):null)endl;return0;}输出入环点值: 2 入环点值: 1 入环点值: null十一、总结阶段操作关键1快慢指针找相遇点快的走2步慢的走1步2双指针找入环点从头节点和相遇点同时走数学原理L kC - M故从头走L步 从相遇点走C-M步 在入环点相遇