LeetCode 的 C++ 实现（七）环形链表（2） ，判断环是否存在，同时找到入口

环形链表（2） ，判断环是否存在，同时找到入口"/>

LeetCode 的 C++ 实现（七）环形链表（2） ，判断环是否存在，同时找到入口

题目

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

Floyd算法思路

1、通过快慢指针来判断是否存在环
2、
入环前的距离是F，第一次点h，以该点将环分割，两段分别距离分别为a 和 b。
可以得到公式：
2(F + a) = F + N(a + b) + a
2F + 2a = F + 2a + b + (N - 1)(a + b)
F = b + (N - 1)(a + b)
所以可以得出，行进F所耗时间，未走了（N-1）圈环，再走一个b的时间

考虑两个极端情况，如果F的距离远大于环的圆周长，可以想象，N讲无穷大，

当F极短时，则会出现，当h点转完一圈，接近入口是才会第一次相遇，即 N = 1，可得出 F = b；

这时如果一个点从h点出发，一个点从链表头出发，当链表头出发的点走到环入口，那么h点出发的点也会走到环入口（走完N -1圈多走一个b到入口，或者 是另一种F = b情况）

3、讲快头，移位到链表头结点，重新以相同速度出发，当两者再次相遇时，刚好到入口

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:ListNode *detectCycle(ListNode *head) {if(head == nullptr || head->next == nullptr)return nullptr;ListNode* fast = head;ListNode* slow = head;while(fast != nullptr && fast->next != nullptr){fast = fast->next->next;slow = slow->next;if(fast == slow)break;}if(fast == nullptr||fast->next == nullptr)return nullptr;fast = head;while(fast != slow){fast = fast->next;slow = slow->next;}return fast;}
};

哈希表

网上有人写的方法，当然这个方法傻得很，就当复习下set的用法吧

如果我们用一个 Set 保存已经访问过的节点，我们可以遍历整个列表并返回第一个出现重复的节

class Solution {
public:ListNode *detectCycle(ListNode *head) {set<ListNode*> visited;ListNode* p = head;while(p != nullptr){if(visited.count(p) > 0){return p;}visited.insert(p);p = p->next;}return nullptr;}
};