【程序员面试金典】面试题 02.08. 环路检测
题目
给定一个有环链表，实现一个算法返回环路的开头节点。
有环链表的定义：在链表中某个节点的next元素指向在它前面出现过的节点，则表明该链表存在环路。
示例 1：
输入：head = [3,2,0,-4], pos = 1
输出：tail connects to node index 1
解释：链表中有一个环，其尾部连接到第二个节点。
示例 2：
输入：head = [1,2], pos = 0
输出：tail connects to node index 0
解释：链表中有一个环，其尾部连接到第一个节点。
示例 3：
输入：head = [1], pos = -1
输出：no cycle
解释：链表中没有环。
进阶：你是否可以不用额外空间解决此题？
思路
- 通过快慢指针是否相交确定是否存在环，如果相交则存在环，否则不存在。
- 如果存在环，重置慢指针为头节点，快指针从相交节点开始后面每次移动一步，如果再次相交，则为环的起始节点。
代码
时间复杂度：O(n)
空间复杂度：O(1)
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
ListNode *fast = head, *slow = head;
bool cycle = false;
while (fast && fast->next) {
fast = fast->next->next;
slow = slow->next;
if (fast == slow) {
cycle = true;
break;
}
}
if (cycle) {
slow = head;
while (fast != slow) {
fast = fast->next;
slow = slow->next;
}
return slow;
}
return nullptr;
}
};