两步走:
- 利用快慢指针判断是否存在环——如果快指针最后指向NULL,则不存在环,否则存在环
- 利用双指针判断入口节点
参照下图,假设图中存在环且快慢指针在C处相遇,设|AB|=a, |BC|=b, |CB|=c
,有2(a+b)=a+b+n(b+c)
,推出a=n(b+c)-b
,因此让两个指针分别从A和C以相同速度前进,两个指针再次相遇的位置即为环的入口节点。
代码如下:
// // Created by jt on 2020/9/23. // class Solution { public: ListNode *detectCycle(ListNode *head) { if (!head) return nullptr; ListNode *fast = head, *slow = head; while(fast && fast->next) { slow = slow->next; fast = fast->next->next; if (slow == fast) { slow = head; while(slow != fast) { slow = slow->next; fast = fast->next; } return slow; } } return nullptr; } };