Write a program to Detect loop in a linked list

The problem, simply

You get the head of a linked list. Normally, if you keep following the next arrows, you reach null and stop. But in a broken chain, the last box may point back to some earlier box, and then you would walk in circles forever.

Say true if the chain has such a loop and false if it ends in null. You do not know the length of the chain, and you cannot mark the boxes.

A story to remember it

Picture it

Examples

Way 1: the simple way

Keep a guest book of every box you have stepped on, a hash set. If you step on a box that is already in the book, you have been here before, so there is a loop. If you reach null, there is none.

Store the box itself, not its number. Two different boxes can hold the same number.

import java.util.*;

class Solution {
    public boolean hasCycle(ListNode head) {
        Set<ListNode> seen = new HashSet<>();     // the boxes themselves
        for (ListNode cur = head; cur != null; cur = cur.next) {
            if (!seen.add(cur)) return true;      // already stepped here
        }
        return false;                             // reached null
    }
}

How long it takes: each box is stepped on once before the repeat, O(n). Extra room: the book holds every box, O(n).

Way 2: the clever way

Two runners: slow moves one box at a time, fast moves two.

1. Both start at the head.
2. While fast and fast.next are not null, move slow one step and fast two steps.
3. If they land on the same box, there is a loop. Say true.
4. If fast reaches the end, there is no loop. Say false.

Why they must meet: once both are inside the loop, every turn fast gains exactly one box on slow. A gap that shrinks by one each turn must reach zero; fast cannot jump over slow.

On a chain without a loop, like 1 -> 2 -> 3 -> 4, fast goes 1, 3, then fast.next.next is null, the loop test fails, and the answer is false.

class Solution {
    public boolean hasCycle(ListNode head) {
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;          // jog one box
            fast = fast.next.next;     // sprint two boxes
            if (slow == fast) return true;
        }
        return false;                  // fast fell off the end
    }
}

How long it takes: before the loop, slow walks at most n boxes; on the loop, fast closes the gap in at most one lap. So O(n). Extra room: two fingers, O(1).

Watch out for

• Test fast != null && fast.next != null in that order. Reading fast.next.next when fast.next is null crashes.
• Compare boxes with ==, not their numbers. Two different boxes can hold the same number without any loop.
• A fast runner moving 3 boxes a turn also works on most loops, but the "gap shrinks by one" proof needs a speed difference of exactly one.

What interviewers ask next

• Where does the loop start? After they meet, put one finger back on the head and move both fingers one box at a time. They meet at the first box of the loop. If the path before the loop has m boxes, walking m boxes forward from the meeting box (going around the loop) lands exactly on the loop start.
• How long is the loop? From the meeting box, walk until you are back, counting steps.
• Remove the loop? Find the start, then find the box whose next is the start, and set its next to null.
• Why can't the hare jump over the tortoise? Each turn the gap changes by exactly one, from d to d - 1, so it must hit zero.
• Where else does this show up? Finding a duplicate number in an array of n + 1 values from 1 to n (LeetCode 287), and checking for "happy numbers": both are hidden loops.

Remember this

Grown-up words: the loop is a cycle, the runners are slow and fast pointers, the whole method is Floyd's cycle detection (the tortoise and the hare), and the guest book is a hash set of nodes.