• The number of the nodes in the list is in the range [0, 10,000]
• -100,000 <= Node.val <= 10,000
• Do not modify the linked list bounds or values

We are given a singly linked list that contains a cycle, and our goal is to pinpoint the exact node where the cycle begins—the "doorway" of the infinite loop. If we simply traverse the list, we will be swept into the loop, running in circles forever without knowing which node originally sent us off course. How can we detect the start of a loop without allocating a massive memory bank to track every node we have already seen?

The most straightforward approach is to write down the memory address of every node we encounter in a hash set. As we step through the list, we cross-reference each node with our records. The very first time we step onto a node that is already saved in our set, we have found our loop entry point.

While this is simple, it requires O(N) memory. If the list contains millions of nodes, keeping a massive bank of breadcrumbs in memory is extremely expensive.

# Store every visited node in a set
seen = set()
curr = head

while curr:
    if curr in seen:
        return curr  # This is the entry node!
    seen.add(curr)
    curr = curr.next

return None  # No cycle found.

To find the entrance using absolutely zero extra memory, we execute the search in two coordinated phases using four pointer states:
- Phase 1 (Collision Detection): We use slow (moves 1 node/step) and fast (moves 2 nodes/step).
- Phase 2 (Entrance Discovery): We use two identical-speed pointers, runner1 (starts at head) and runner2 (starts at the collision site). Both advance exactly one node at a time.

To understand why this works, we look at the mathematical symmetry of the track:
- Let A be the distance from the head to the loop entrance.
- Let B be the distance from the loop entrance to the collision site.
- Let C be the total length of the circular loop.

During Phase 1, slow covers a distance of A + B, while fast covers A + B + C (completing one full circle). Since fast runs exactly twice as fast as slow, we can set up a simple equation:

2 * (A + B) = A + B + C => A + B = C => A = C - B

This elegant equation proves that the distance from the start of the list to the loop entrance (A) is exactly equal to the remaining distance from the collision site to the entrance (C - B). Therefore, if we place one runner at the head and another at the collision site and march them forward at the exact same speed, they will inevitably meet right at the entrance!

We first run Phase 1 to detect a collision. If fast or fast.next becomes null, there is no loop and we return null. If they meet, we immediately halt the sprinter, place one pointer back at head, and march both pointers forward one step at a time until they meet.

slow = head
fast = head

# Phase 1: Detect collision
while fast and fast.next:
    slow = slow.next
    fast = fast.next.next
    if slow == fast:
        break
else:
    return None # Sprinter reached the end of a straight track, no cycle!

# Phase 2: Find the doorway
runner1 = head
runner2 = slow

while runner1 != runner2:
    runner1 = runner1.next # Move 1 step
    runner2 = runner2.next # Move 1 step

# Both meet at the loop entrance
return runner1

The phase-shift strategy handles boundary situations seamlessly:
- No Cycle Exists: The while...else block catches a null termination and exits safely before Phase 2 runs.
- Loop Starts at Head (e.g. Node 1 loops to Node 1): The collision occurs right at head. In Phase 2, runner1 and runner2 both start at head, the equality condition is instantly satisfied, and the loop is skipped, returning the correct entrance.