Find the starting point of the loop

The problem, simply

You get the head of a linked list. Maybe the last box points to null. Maybe it points back to some earlier box, which makes a loop.

If there is a loop, give back the box where the loop begins: the first box you would visit twice if you kept walking. If there is no loop, give back null. You may not change the list.

A story to remember it

Picture it

Examples

Way 1: the simple way

Carry a bag, a hash set. Put every box you step on into the bag. The first time you step on a box that is already in the bag, that box is where the loop begins, because it is the first box you ever see twice.

1. Start at the head with an empty bag.
2. If the box is in the bag, return it.
3. Otherwise add it and step forward. If you reach null, return null.

class Solution {
    public ListNode detectCycle(ListNode head) {
        Set<ListNode> seen = new HashSet<>();   // stores boxes, not values
        for (ListNode curr = head; curr != null; curr = curr.next) {
            if (!seen.add(curr)) return curr;   // add says false if it was there already
        }
        return null;
    }
}

How long it takes: each box goes into the bag once, O(n). Extra room: the bag holds every box, O(n).

Way 2: the clever way

Use the two cars, a slow pointer and a fast pointer.

1. Phase one: move slow one step and fast two steps until they meet. If fast reaches null, there is no loop.
2. Phase two: put slow back on the head. Leave fast where they met. Move both one step at a time.
3. The box where they meet in phase two is where the loop begins.

Why it works, in numbers. Say the driveway has a boxes, the loop has L boxes, and they met b steps into the loop. Slow drove a + b steps and fast drove 2(a + b). The extra a + b steps of the fast car were whole laps, so a + b is a multiple of L. From the meeting spot, a more steps make a + b steps into the loop, which is a whole number of laps, so you are back at the gate. A car leaving the parking lot also needs a steps to reach the gate. They arrive together.

class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;              // one step
            fast = fast.next.next;         // two steps
            if (slow == fast) {            // they met inside the loop
                slow = head;               // back to the parking lot
                while (slow != fast) {
                    slow = slow.next;      // both drive at the same speed now
                    fast = fast.next;
                }
                return slow;               // the gate of the loop
            }
        }
        return null;                       // fast found the end, no loop
    }
}

How long it takes: phase one ends within about a + L steps of slow, and phase two takes a steps, so O(n). Extra room: two pointers, O(1).

Watch out for

• Comparing values instead of boxes. Use slow == fast on the nodes. Two different boxes can hold the same number.
• Checking fast.next.next without first checking fast != null && fast.next != null. A plain list then crashes.
• Starting fast at head.next while slow starts at head. Then the phase two math is off by one and you get the wrong box. Start both at the head.
• Moving fast two steps in phase two. Both must move one step.

What interviewers ask next

• How long is the loop? After the first meeting, keep fast still and walk slow around until it returns. The number of steps is L.
• Remove the loop. Find the gate with phase two, then walk from the gate around the loop to the box whose next is the gate and set that next to null.
• Find a duplicate in an array of n + 1 numbers from 1 to n without changing it (LeetCode 287). Treat i -> nums[i] as a next arrow. The duplicate is the gate of the loop, found with the same two phases.
• Why is fast guaranteed to land on slow and not jump over it? Once both are in the loop, each round fast gains exactly one step on slow, so the gap shrinks 1 at a time and hits 0.

Remember this

Grown-up words: the driveway is the part of the list before the cycle, the ring is the cycle, the gate is the cycle's entry node, the bag is a hash set, and the two cars are Floyd's tortoise and hare algorithm.