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

class Solution:
    def detectCycle(self, head: ListNode) -> ListNode:
        # edge case
        if head == None:
            return None
        
        # regular case 
        slow = head
        fast = head.next
        
        while slow != fast:
            if fast == None or fast.next == None:
                return None
            slow = slow.next
            fast = fast.next.next
            
        # s+m+br+1 = 2(s+m+ar) -> s=nr+1-m=r-m+1
        # let start meet slow
        start = head
        while start != slow.next:
            start = start.next
            slow = slow.next
            
        return start