企业官网建设流程全解析

前言

本专栏文章为《LeetCode 热题 100》的刷题题解，相关内容如有侵权，立即删除。

一、题目

1、原题链接

142.环形链表 II

2、题目描述

二、个人思路整理

1、思路分析

也可以参考博主的该博客【代码随想录】LC 142. 环形链表 II

核心思路：Floyd判圈算法（快慢双指针法）

1. 判断是否有环

• 定义两个指针：慢指针slow每次走 1 步，快指针fast每次走 2 步。
• 如果fast遇到nullptr，说明链表无环，直接返回nullptr。
• 如果fast和slow相遇，说明链表必定有环。

2. 寻找入环点

假设

• 头节点到入环点的距离为a aa
• 入环点到首次相遇点的距离为b bb
• 首次相遇点继续走到入环点的距离为c cc（环的总长度为b + c b + cb+c）

相遇时各指针走的距离：

• slow走的步数：S = a + b S = a + bS=a+b
• fast走的步数：F = a + n ( b + c ) + b F = a + n(b + c) + bF=a+n(b+c)+b（其中n ≥ 1 n \ge 1n≥1为快指针在环内转的圈数）

根据快指针速度是慢指针的 2 倍：
F = 2 S ⟹ a + n ( b + c ) + b = 2 ( a + b ) F = 2S \implies a + n(b + c) + b = 2(a + b)F=2S⟹a+n(b+c)+b=2(a+b)a = n ( b + c ) − b = ( n − 1 ) ( b + c ) + c a = n(b + c) - b = (n - 1)(b + c) + ca=n(b+c)−b=(n−1)(b+c)+c

结论：

• 当n = 1 n = 1n=1时，a = c a = ca=c。
• 这意味着：从链表头节点出发一个指针，同时从相遇点出发一个指针，两者每次均走 1 步，最终必定会在入环点相遇。

2、解题代码

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */classSolution{public:ListNode*detectCycle(ListNode*head){ListNode*fast=head;ListNode*slow=head;// 1. 判断是否有环while(fast!=nullptr&&fast->next!=nullptr){fast=fast->next->next;slow=slow->next;// 快慢指针相遇，说明有环if(fast==slow){// 2. 寻找环入口ListNode*p1=head;ListNode*p2=slow;while(p1!=p2){p1=p1->next;p2=p2->next;}returnp1;// 相遇点即为入环节点}}returnnullptr;// 无环}};

复杂度分析

• 时间复杂度：O ( N ) O(N)O(N)。寻找相遇点和寻找入口节点各遍历最多2 N 2N2N次。
• 空间复杂度：O ( 1 ) O(1)O(1)。仅使用常数个指针变量。

三、知识风暴

Floyd 判圈算法（快慢双指针法）是本题的核心思想：用一快一慢两个指针遍历链表，通过「快指针能否追上慢指针」来判断是否存在环，并在相遇后通过数学推导定位入环点。它把空间复杂度从哈希表的O ( n ) O(n)O(n)优化到O ( 1 ) O(1)O(1)。

算法核心思想：

• 快慢指针：慢指针slow每次走 1 步，快指针fast每次走 2 步，二者从head同时出发。
• 判环依据：若无环，fast会先遇到nullptr；若有环，fast最终必定追上slow并相遇。
• 相遇点定位：相遇后，从head和相遇点各出发一个指针，每次走 1 步，二者必定在入环点相遇。
• 数学推导：设头节点到入环点距离为a aa，入环点到相遇点距离为b bb，环长为L LL，由2 ( a + b ) = a + b + n L 2(a+b) = a + b + nL2(a+b)=a+b+nL可推出a = n L − b a = nL - ba=nL−b，即从相遇点继续走到入环点的距离与a aa相等。

常见对比：哈希表 vs 快慢指针

使用要点：

• 判空处理：head为空或只有一个节点时，链表不可能有环，直接返回nullptr。
• 循环条件：while (fast != nullptr && fast->next != nullptr)，保证fast->next->next不越界。
• 相遇判断：fast == slow说明有环；若循环正常结束，说明fast走到了链表末尾，无环。
• 入环点定位：相遇后令p1 = head、p2 = slow，二者同步走 1 步，首次相等处即为入环点。
• 边界情况：环可能包含整个链表（入环点即head），此时p1与p2在head处直接相等。

算法变体与扩展：

1. 只判断是否有环：使用快慢指针，相遇即返回true，无需定位入环点（对应 LeetCode 141）。
2. 返回入环点：在相遇后增加一步数学定位，即本题 142 的做法。
3. 求环的长度：相遇后让一个指针原地不动，另一个指针每次走 1 步，再次相遇时走过的步数即为环长。
4. 求链表长度：先定位入环点，再分别计算头节点到入环点、以及环的长度，二者相加即为链表总长。

常见对比：三种指针遍历写法

与其他算法的对比：

• 快慢指针（Floyd 判圈）：O ( n ) O(n)O(n)时间、O ( 1 ) O(1)O(1)空间，是本题最优解，也是面试中最常考察的解法。
• 哈希表判环：O ( n ) O(n)O(n)时间、O ( n ) O(n)O(n)空间，思路最简单，但额外占用内存，不满足进阶要求。
• 暴力遍历：对每个节点向后遍历判断是否回到自身，O ( n 2 ) O(n^2)O(n2)时间，仅适用于理解思路，不具实用性。

相关 LeetCode 例题：

• 141. 环形链表（快慢指针判环，本题的前置基础）
• 142. 环形链表 II（本题，判环 + 定位入环点）
• 287. 寻找重复数（快慢指针思想在数组上的应用）
• 202. 快乐数（快慢指针判断循环的经典应用）

指针声明风格：ListNode* p与ListNode *p

在 C++（以及 C 语言）中，ListNode* p与ListNode *p在编译器语法、生成的目标代码、运行效率和功能上没有任何区别，差异仅体现在设计哲学与代码风格上：

• ListNode* p（星号靠向类型）：强调p的类型是ListNode*，契合“类型在前”的直觉，是现代 C++ 及 Java/C# 转 C++ 开发者偏好的写法。
• ListNode *p（星号靠向变量名）：强调*p解引用后得到ListNode，是 C 语言传统风格，在 Linux 内核、STL 源码中极为常见。

关键陷阱：*修饰符只与其紧邻的变量名绑定。ListNode* p1, p2;中只有p1是指针，p2是普通对象；而ListNode *p1, *p2;则两个都是指针。建议一行只声明一个指针变量，彻底避免混淆。

回到本题：解题代码中ListNode *detectCycle(ListNode *head)与ListNode* fast = head;混用了两种风格，但功能完全等价，理解这一区别有助于快速抓住源码本质。