哈希表

最直观的思想，哈希表记录遍历的结点，如果结点重复出现，则有环。如果遍历到空结点，无环。

class Solution {
public:ListNode *detectCycle(ListNode *head) {unordered_set ad;auto tail = head;while(tail&&!ad.count(tail)){ad.insert(tail);tail = tail ->next;}if(!tail) return NULL;return tail;}
};

1. 时间复杂度 : O(n)O(n)O(n) ， nnn 是结点的数量，一次遍历的时间复杂度 O(n)O(n)O(n) 。
2. 空间复杂度 : O(n)O(n)O(n) ， 哈希表的空间复杂度 O(n)O(n)O(n) 。

快慢指针

力扣官解的图很好了，形象证明建议看那个图，我说一下数学证明。链接 : 环形链表 II

设第一次相遇时， fastfastfast 转了 nnn 圈，有
①a+n(b+c)+b=a+(n+1)b+nca+n(b+c)+b=a+(n+1)b+nca+n(b+c)+b=a+(n+1)b+nc 表示快指针走过的结点数，

此时 slowslowslow 走了 a+ba+ba+b ，又快指针是慢指针的二倍速，有
②2(a+b)=a+(n+1)b+nc2(a+b)=a+(n+1)b+nc2(a+b)=a+(n+1)b+nc
整理，得
③a=(n−1)b+nca=(n-1)b+nca=(n−1)b+nc
分析含义， b+cb+cb+c 是环的长度，可以提取上式的 n−1n-1n−1 圈，有
④a=(n−1)(b+c)+ca=(n-1)(b+c) + ca=(n−1)(b+c)+c
快慢指针相遇点和入环点的距离 ccc ，从相遇点走 ccc 步，就能到达入环点。
到达入环点再走 kkk 圈还是入环点，也就是说， slowslowslow 再走 aaa 步可以到达入环点，相当于走了 ccc 步，又走了 n−1n-1n−1 圈。

快慢相遇后，设从起始点出发的 temptemptemp ，从相遇点出发的 slowslowslow ， temptemptemp 到达入环点时，刚好走过 aaa 的距离， slowslowslow 走过 aaa 的距离也到入环点。即 slowslowslow 和 temptemptemp 的相遇点，就是入环点。

class Solution {
public:ListNode *detectCycle(ListNode *head) {auto slow = head,fast = head;while(fast){slow = slow->next;if(!fast->next) return NULL;fast = fast->next->next;if(slow==fast) break;}if(!fast) return NULL;auto temp = head;while(temp!=slow){temp = temp ->next;slow = slow ->next;}return slow;}
};

1. 时间复杂度 : O(n)O(n)O(n) ， nnn 是结点的数量，快慢指针相遇走过的结点数量，是 nnn 的常数倍， temptemptemp 指针和慢指针相遇走过的结点数量，是 nnn 的常数倍，忽略常数时间复杂度 O(n)O(n)O(n) 。
2. 空间复杂度 : O(1)O(1)O(1) ， 只使用常量级空间 。

AC

致语

• 理解思路很重要
• 读者有问题请留言，清墨看到就会回复的。