142. Linked List Cycle II (https://leetcode.com/problems/linked-list-cycle-ii/): Given a linked list, return the node where the cycle begins. If there is no cycle, return null. To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, th…

142. Linked List Cycle II (#1 Two pointer).java

// Two pointer solution: slow/fast pointers
// Time: O(n), 0ms
// Space: O(1), 36mb
public class Solution {
    public ListNode detectCycle(ListNode head) {
        // Slow fast pointer
        ListNode slow = head, fast = head;
        while(fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if(slow == fast) break;
        }
        
        // No cycle in the list
        if(fast == null || fast.next == null) return null;
        
        // Find where the cycle begins (proof below)
        slow = head;
        while(slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }
        
        return slow;
    }
}
/*
Say the cycle begin at s1. slow and fast pointer meet at s2 step after the cycle begins.
And there are s3 steps before the cycle ends. s1 and s2 meet after k step of slow pointer.
fast is one loop faster than the slow: 2k - k = s2 + s3
k steps of slow: k = s1 + s2
So we have s1 = s3
So let the slow pointer begin from head (s1), and let the fast pointer begin from where they met (s3).
They will meet at the beginning of the cycle.
*/

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */