Detect whether a linked list has a cycle, and return the node where the cycle begins.

The cheap answer and why to move past it

Walk the list putting each node into a hash set and stop when you see one twice. That is O(n) time, O(n) space, and it hands you the cycle entry immediately with no cleverness. Say it, because it proves you understand the problem, then say why you would not ship it: on a list of millions of nodes the set is the dominant memory cost, and the constant-space version is not appreciably harder.

Floyd's approach keeps two pointers moving at different speeds through the same list. If the list terminates, the faster pointer reaches the end and you are done. If it does not, the faster pointer enters the cycle and closes the gap on the slower one by exactly one node per step, so it cannot overshoot without landing on it, and a meeting is guaranteed within one cycle length.

The code

ListNode detectCycle(ListNode head) {
    ListNode slow = head, fast = head;

    while (fast != null && fast.next != null) {   // this order is not interchangeable
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) {                       // a meeting, but NOT the entry node
            ListNode probe = head;
            while (probe != slow) {
                probe = probe.next;
                slow = slow.next;
            }
            return probe;                         // both are now at the cycle entry
        }
    }
    return null;                                  // fast fell off the end: no cycle
}

The guard is where careless answers fail. fast != null has to be evaluated first because fast.next dereferences it, and Java's && short-circuits precisely to make that safe. Testing fast.next != null && fast != null throws on an empty list. Both pointers start at head, so the equality test has to sit after both advances. Placed at the top of the loop body it fires on the very first iteration on every input, cycle or not, and reports the head as the answer. That pairing - where the pointers start and where you compare them - has to be decided together rather than assembled from two half-remembered versions.

Why resetting to the head works

This is the part interviewers actually probe, because it separates a memorised routine from an understood one. Let L be the number of steps from the head to the cycle entry, C the cycle length, and k the number of steps from the entry to the meeting point.

When they meet, the slow pointer has taken L + k steps and the fast pointer has taken twice that. The fast pointer's path is also L + k plus some whole number of laps, so 2(L + k) = L + k + nC, which reduces to L + k = nC, and therefore L = nC - k.

Now start one pointer at the head and leave the other at the meeting point, and advance both by L. The first arrives at the entry by definition. The second travels nC - k steps forward from position k inside the cycle, landing at nC, which is the entry after n complete laps. They arrive together, which is why the equality test in the second loop is the answer rather than a coincidence.

Note what this does not require: n is not computed anywhere, and the argument holds for any list where the tail is long relative to the cycle or the reverse.

Pointer surgery has one recurring failure

Every non-trivial linked-list operation loses a pointer it still needed, and reversal is the clearest instance. Overwriting curr.next destroys the only reference to the rest of the list, so the successor must be saved first.

ListNode reverse(ListNode head) {
    ListNode prev = null, curr = head;
    while (curr != null) {
        ListNode next = curr.next;   // save it before the next line destroys it
        curr.next = prev;
        prev = curr;
        curr = next;
    }
    return prev;                     // head is now the tail; returning head yields a one-node list
}

Returning head instead of prev is the off-by-one of linked lists: the function has done all its work correctly and then hands back a pointer to the node that is now the final element, so the caller sees a list of length one. It compiles, it does not crash, and it fails on any input longer than a single node.

The general habit that prevents both classes of error is to name the invariant before writing the loop. For reversal it is that everything before curr has already been reversed and prev is its new head. For cycle detection it is that slow has taken exactly half as many steps as fast. When a loop body breaks its invariant the bug is visible on the page rather than in a debugger.