Linked List Cycle II

Intuition

First we use the classic tortoise-and-hare collision to confirm a loop exists and to find some node inside it. The key insight is arithmetic: when the slow and fast pointers meet, the distance from the head to the cycle entry equals the distance from the meeting point to that same entry, measured around the loop. That is why resetting one pointer back to the head and then advancing both pointers one step at a time makes them collide exactly at the start of the cycle. If the fast pointer instead reaches null, there is no loop and we return null. The whole process stays in constant space.

Algorithm walkthrough

1. 1Run slow (one step) and fast (two steps) from the head until they either meet or fast falls off the end.
2. 2If fast or fast.next becomes null, there is no cycle, so return null.
3. 3When slow equals fast, a cycle is confirmed; place a new pointer ptr at the head.
4. 4Advance ptr and slow together one node at a time.
5. 5The node where ptr and slow meet is the entrance of the cycle; return it.

Implementation

class Solution:
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow is fast:
                ptr = head
                while ptr is not slow:
                    ptr = ptr.next
                    slow = slow.next
                return ptr
        return None