[Leetcode] Linked List Cycle I and II

Problem 

Given a linked list, determine if it has a cycle.
Return the node where the cycle begins. If there is no cycle, return null.
Follow up: Can you solve it without using extra space?
Follow up: Can you find the length of the cycle ? Then the length of the linked list ?

Algorithm 

Slow and Fast Pointer

Use a slow pointer S with velocity 1 and a fast pointer F with velocity 2 to traverse the linked list. If there is no cycle, the F will always be in front of the S, and finally F = null or F.next = null. If there is cycle, both F and S will be trapped in the cycle. 

Claim: If there is a cycle in the linked list, pointer S and pointer F will meet in O(n) steps. 

Proof: since F has velocity 2, it will enter the cycle first. Assume, when S enters the cycle, F has a position k in the cycle. Since F moves 1 more step than S in each unit time, it will catch up with S in C-k time, where C is the total length of the cycle. Since C = O(n), S and F will meet in O(n) steps. 

Entrance of the Cycle

Assume the linked list has a cycle with length C, and the rest has a length L. When S enters the cycle, F has a position k in the cycle, where 0<= k < C. Therefore, during the time S moves length L, F moves m*C+k, i.e. L = (L+m*C+k)/2. So, L = m*C + k. 

When S enters the cycle, F is C-k steps behind the S. Each unit time, F catches up one step. After C-k steps, S and F will meet at position C-k. 

Let the F pointer continues with velocity 2. Since it is on position C-k, it can move m*C+k steps in time L. So, we can release anther pointer from the head. This pointer will meet the F at the entrance of the cycle. 

Code