142. Linked List Cycle II

Assume fast goes 2k steps and slow goes k steps, then they meet. Assume slow goes $k=s+m$steps, fast goes $2k=s+m+ar$ steps, $a > b$ .

So in math, $2k=2(s+m)=s+m+ar$

Obviously, $s+m =nr, s = nr-m$

Assume $n=1, s = r-m$ (fast only need to step one round more than 2*slow)

When slow = fast, let slow continues moving and start move at the same time at the same step until they meet. The steps start walks is the circle meeting.

Initializestart = head and slow = head. After they move then compare them.

Java

public class Solution {
    public ListNode detectCycle(ListNode head) {
        if(head == null || head.next == null) return head;
        
        ListNode slow = head;
        ListNode fast = head.next;
        while(fast != slow) {
            if(fast == null || fast.next == null)
                return null;
            slow = slow.next;
            fast = fast.next.next;
        }
        
        // find the s = r - m + 1
        // 两个pointer再走r-m步就能在s处相遇
        ListNode start = head;
        while(start != slow.next) {
            start = start.next;
            slow = slow.next;
        }
        return start;
    }
}

Python