解密链表环的起点：LeetCode 142 题

解密链表环的起点：LeetCode 142 题

• 视频地址
• 🌟 引言
• 🔍 问题描述
• 🧠 解题思路回顾
  • 快慢指针算法
  • 数学原理
• 💻 C++代码实现
• 🛠 代码解析
  • 数据结构定义
  • 算法实现细节
• 🚀 性能分析
• 🐞 常见问题与调试
  • 常见错误
  • 调试技巧
• 📊 复杂度对比表
• 🌈 总结

视频地址

因为想更好的为大佬服务，制作了同步视频，这是Bilibili的视频地址

🌟 引言

链表环检测问题在C++中同样是一个经典面试题。本文将用C++实现LeetCode 142题"环形链表II"的解决方案，深入讲解快慢指针算法的原理和实现细节。

🔍 问题描述

给定一个链表的头节点 head，返回链表开始入环的第一个节点。如果链表无环，则返回 nullptr。

🧠 解题思路回顾

快慢指针算法

1. 使用两个指针：slow每次走一步，fast每次走两步
2. 如果两指针相遇，说明链表有环
3. 将其中一个指针重置到链表头，然后两指针以相同速度前进
4. 再次相遇的位置就是环的起点

数学原理

设：

• 链表头到环起点距离：a
• 环起点到相遇点距离：b
• 相遇点到环起点距离：c

则有：

• 第一次相遇时：slow走了a+b，fast走了a+b+c+b
• 因为fast速度是slow的两倍：2(a+b) = a+2b+c
• 推导得：a = c

💻 C++代码实现

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */classSolution{public: ListNode *detectCycle(ListNode *head){// 边界条件处理if(head ==nullptr|| head->next ==nullptr){returnnullptr;} ListNode *slow = head; ListNode *fast = head;// 第一阶段：检测是否有环while(fast !=nullptr&& fast->next !=nullptr){ slow = slow->next; fast = fast->next->next;if(slow == fast){break;// 相遇说明有环}}// 检查是否因为无环退出循环if(fast ==nullptr|| fast->next ==nullptr){returnnullptr;}// 第二阶段：寻找环起点 slow = head;// 重置慢指针到头部while(slow != fast){ slow = slow->next; fast = fast->next;}return slow;// 相遇点即为环起点}};

🛠 代码解析

数据结构定义

structListNode{int val; ListNode *next;ListNode(int x):val(x),next(NULL){}};

这是LeetCode标准的链表节点定义，包含一个整数值和指向下一个节点的指针。

算法实现细节

寻找环起点：

slow = head;// 重置慢指针到头部while(slow != fast){ slow = slow->next; fast = fast->next;}

根据数学推导，两指针以相同速度前进，再次相遇点即为环起点。

无环检查：

if(fast ==nullptr|| fast->next ==nullptr){returnnullptr;}

如果因为快指针无法前进而退出循环，说明无环。

环检测阶段：

while(fast !=nullptr&& fast->next !=nullptr){ slow = slow->next; fast = fast->next->next;if(slow == fast){break;// 相遇说明有环}}

快指针每次走两步，慢指针每次走一步，直到相遇或快指针无法前进。

指针初始化：

ListNode *slow = head; ListNode *fast = head;

快慢指针都从头节点开始。

边界条件处理：

if(head ==nullptr|| head->next ==nullptr){returnnullptr;}

处理空链表或单节点链表的特殊情况。

🚀 性能分析

• 时间复杂度：O(n)
  • 最坏情况下需要遍历链表两次
• 空间复杂度：O(1)
  • 只使用了固定数量的指针变量

🐞 常见问题与调试

常见错误

1. 初始条件处理：
   忘记处理空链表或单节点链表的情况。
2. 指针重置错误：
   在第二阶段错误地重置了快指针而不是慢指针。

空指针访问：

while(fast !=nullptr&& fast->next !=nullptr)

必须同时检查fast和fast->next，否则可能访问空指针的next成员。

调试技巧

1. 小规模测试：
   • 无环链表：1->2->3->null
   • 有环链表：1->2->3->4->2（环在节点2）
2. 边界测试：
   • 空链表
   • 单节点自环链表
   • 双节点互相指向的链表

打印指针地址：

cout <<"Slow: "<< slow <<" Fast: "<< fast << endl;

帮助跟踪指针移动情况。

📊 复杂度对比表

🌈 总结

通过C++实现的快慢指针算法，我们能够高效地解决链表环检测问题。关键在于：

1. 理解快慢指针相遇的数学原理
2. 正确处理边界条件和指针访问

分两个阶段实现：环检测和环起点定位

这种方法不仅高效（O(n)时间，O(1)空间），而且体现了算法设计的巧妙之处。掌握这个技巧，你就能轻松应对链表相关的各种环检测问题了！