解题思路:
\qquad 之前在 环形链表I 中讲过利用快慢指针判断链表是否有环,当快慢指针相等时,链表中存在环。但环形链表II在其基础上,额外需要找到环的第一个节点,可以在快慢指针相遇的基础上,进一步分析。
\qquad 如果链表存在环,则快慢指针相遇于环上一点(如下图),将链表拆分成a, b, c
三段,题目需要返回a、b
段交界点的指针,由快慢指针相遇可得:
a = n ( b + c ) − b a = n(b+c) - b a=n(b+c)−b
a = c + ( n − 1 ) ( b + c ) a = c + (n-1)(b+c) a=c+(n−1)(b+c)
\qquad 此时,如果使用两个指针分别从表头和相遇点开始移动,则这两个指针会相遇于环开始的节点,此时返回结果即可。
ListNode *detectCycle(ListNode *head) {ListNode* slow = head;ListNode* fast = head;ListNode* pos = head;while(fast != nullptr){slow = slow->next;if(fast->next != nullptr){fast = fast->next->next;}else return nullptr;if(slow == fast){while(pos != slow){slow = slow->next;pos = pos->next;}return pos;}}return nullptr;}