力扣(LeetCode)142. 环形链表 II(C++)

力扣(LeetCode)142. 环形链表 II(C++)

哈希表

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

class Solution {
public:ListNode *detectCycle(ListNode *head) {unordered_set<ListNode *> 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) ， n n n 是结点的数量，一次遍历的时间复杂度 O ( n ) O(n) O(n) 。
2. 空间复杂度 : O ( n ) O(n) O(n) ， 哈希表的空间复杂度 O ( n ) O(n) O(n) 。

快慢指针

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

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

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

快慢相遇后，设从起始点出发的 t e m p temp temp ，从相遇点出发的 s l o w slow slow ， t e m p temp temp 到达入环点时，刚好走过 a a a 的距离， s l o w slow slow 走过 a a a 的距离也到入环点。即 s l o w slow slow 和 t e m p temp temp 的相遇点，就是入环点。

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) ， n n n 是结点的数量，快慢指针相遇走过的结点数量，是 n n n 的常数倍， t e m p temp temp 指针和慢指针相遇走过的结点数量，是 n n n 的常数倍，忽略常数时间复杂度 O ( n ) O(n) O(n) 。
2. 空间复杂度 : O ( 1 ) O(1) O(1) ， 只使用常量级空间 。

AC

致语

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