[LeetCode 142] Linked List Cycle II

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

Note: Do not modify the linked list.

Follow up:
Can you solve it without using extra space?

Diffculty
Medium

Similar Problems

Analysis

(E) Linked List Cycle (H) Find the Duplicate Number

1. 如果有环，如何判断环的起始点。 假设linked list从head到环起始点s的长度为L，环的周长为C（两节点之间的长度为之间link的数量） 当fast与slow第一次相遇的位置记为m1，并假设m1离开环起始点s距离X，由于fast走的总路程一定是slow的两倍： (L + X)2 = L + nC + X => L = nC - X 从m1出发，走nC - X的路程将回到s，而这段路程正好等于head到s之间的路程！所以第一次相遇后，将slow移到head， 然后slow/fast同时以一次走一步的速度前进，直到它们第二次相遇，便是s了。

// http://blog.csdn.net/kenden23/article/details/13871699 class Solution { public: ListNode detectCycle(ListNode head){ if (!head || !head->next) return nullptr; ListNode slow = head->next; ListNode fast = head->next->next; while (fast && fast != slow){ slow = slow->next; fast = fast->next? fast->next->next:fast->next; } if (fast == nullptr) return nullptr; for (fast = head; fast != slow; fast = fast->next) slow = slow->next; return slow; } };