Leetcode: Linked List Cycle II

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

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

Understand the problem:
The question is closed to determine a linked list has a cycle. The question asks for if a cycle exists, find its entrance. For e.g.,  for a cycled linked list:
1 -> 2  -> 3  ->4  ->2
The entrance of the cycle is 2.

Naive Solution:
Again, the native solution could use a hash table to store the elements we visited before. If we found a duplicated element, then that element is the entrance of the cycle. 

As we can see, the solution is straight-forward. The time complexity is O(n). The space complexity is O(n) as well since we need to store the nodes in the hash table. 

A Better Solution:
A better solution without using hash table is, we first find the collision point in the loop. Then move two pointers at the same speed, one starts from the head of the linked list, while the other starts from the collision node. The next collision is the entrance of the loop.

Code (Java):

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        // Find the collision point if the list has a cycle
        if (head == null) return null;
        
        ListNode slow = head;
        ListNode fast = head;
        
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            
            if (slow == fast) break;
        }
        
        // check if the list has no cycle
        if (fast == null || fast.next == null) 
            return null;
        
        // find the entrance of the cycle
        slow = head;
        while (slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }
}

Discussion:
The mathematical proof is way of complicated. There are many online resources to prove that. Frankly, I don't think this gonna be a good interview question, because the solution is too tricky and requires too much mathematical proof. If you never seen that problem before, it is very hard to come out the solution from scratch at the code interview.  

Follow up: How to know the length of the cycle?
It is not hard to come up with the solution. From the collision point in the cycle, use two pointers, one moves one step at a time while the other moves two at a time. Until they meet again, the number of steps is the length of the cycle. 

It is relatively easy to understand the idea. From the collision point, one stand still while the other moves one step at a time, the next they meet, the moving pointer must move one cycle. 

Summary:
This question composed the three classic questions in the circular linked list:
1. Determine a linked list have a cycle?
2. If yes, what is the entrance node of the cycle?
3. If yes, what is the length of the cycle?
Be familiar with the solutions.