Detect a Loop in a Linked List in Java with Floyd’s Algorithm

To detect a loop in a linked list, we move two pointers from the head, a slow one by one node and a fast one by two nodes per step, and the list has a loop if the two pointers ever reach the same node. This method is Floyd’s cycle detection algorithm, also called the tortoise and hare algorithm. It takes O(n) time and O(1) extra memory.

Interviewers ask this question to test pointer handling and null checks. The same check protects real code that follows links between records, such as manager chains, parent categories or redirect rules, where a bad link would make a loop run forever.

The following example builds a five-node list, checks it, links the last node back to the second node and checks it again with the hasCycle() method from section 2.

Node head = listOf(1, 2, 3, 4, 5);
boolean before = hasCycle(head);             // false
nodeAt(head, 4).next = nodeAt(head, 1);      // node 5 points back to node 2
boolean after = hasCycle(head);              // true

Notice that the check never changes the list and never catches an exception to find the end. We trace the pointers step by step, find where the loop starts, measure and remove the loop, and compare Floyd’s algorithm with a HashSet and other options.

1. Why the Tortoise and the Hare Meet

In a list without a loop, the fast pointer reaches null after about n/2 steps, and the method returns false. In a list with a loop, neither pointer ever reaches null, so both end up circling inside the loop.

Once both pointers are in the loop, the fast pointer moves one node closer to the slow pointer on every step, because it moves two nodes while the slow pointer moves one. The gap shrinks by one node per step, so the fast pointer cannot jump over the slow one, and they meet before the slow pointer completes one lap.

Step	slow	fast	Same node?
0	1	1	Start
1	2	3	No
2	3	5	No
3	4	3 (5, 2, 3)	No
4	5	5 (4, 5)	Yes, loop found

The meeting node is not the start of the loop. In our list, the pointers meet at node 5, whereas the loop starts at node 2, and section 3 shows how to get from one to the other.

2. Detect a Loop in a Linked List with Floyd’s Algorithm

The puzzle uses a hand-written singly linked list, because java.util.LinkedList keeps its nodes private and its methods never create a loop. Each node holds a value and a reference to the next node, and two small helpers build test lists. The full program is in the Core-Java repository.

class Node {
    final int value;
    Node next;

    Node(int value) {
        this.value = value;
    }
}

static Node listOf(int... values) {
    Node dummy = new Node(0);
    Node tail = dummy;
    for (int v : values) {
        tail.next = new Node(v);
        tail = tail.next;
    }
    return dummy.next;
}

static Node nodeAt(Node head, int index) {
    Node current = head;
    for (int i = 0; i < index; i++) {
        current = current.next;
    }
    return current;
}

The hasCycle() method moves both pointers until the fast pointer runs off the end of the list or catches the slow pointer. The loop condition checks fast and fast.next, so fast.next.next never throws a NullPointerException.

static boolean hasCycle(Node head) {
    Node slow = head;
    Node fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;                 // one step
        fast = fast.next.next;            // two steps
        if (slow == fast) {
            return true;                  // same node object
        }
    }
    return false;                         // fast reached the end
}

The method compares nodes with ==, not equals(), because a loop means the same node object appears twice, not two nodes with equal values. A list such as 1, 2, 1, 2 has repeated values and no loop.

boolean empty = hasCycle(null);                     // false
Node one = listOf(7);
boolean single = hasCycle(one);                      // false
one.next = one;
boolean selfLoop = hasCycle(one);                    // true
boolean repeated = hasCycle(listOf(1, 2, 1, 2));     // false

3. Finding Where the Loop Starts

Interviewers often follow up with a request for the first node of the loop. Floyd’s algorithm answers it with a second phase. After the pointers meet, we move one pointer back to the head and advance both pointers one node at a time, and they meet again at the start of the loop.

The second phase works because of a distance fact. If the head is m nodes before the loop start, walking m nodes forward from the meeting point also lands on the loop start, after zero or more full laps. So both pointers reach the loop start after the same m steps.

static Node meetingPoint(Node head) {
    Node slow = head;
    Node fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) {
            return slow;
        }
    }
    return null;                          // no loop
}

static Node loopStart(Node head) {
    Node meet = meetingPoint(head);
    if (meet == null) {
        return null;
    }
    Node p = head;
    while (p != meet) {
        p = p.next;
        meet = meet.next;
    }
    return p;
}

Node looped = listOf(1, 2, 3, 4, 5);
nodeAt(looped, 4).next = nodeAt(looped, 1);
int meetValue = meetingPoint(looped).value;          // 5
int startValue = loopStart(looped).value;            // 2

3.1. Loop Length and Loop Removal

From the meeting point, one pointer walks around the loop until it returns, and the number of steps is the loop length. To remove the loop, we find the last node of the loop, whose next is the loop start, and set its next to null.

static int loopLength(Node head) {
    Node meet = meetingPoint(head);
    if (meet == null) {
        return 0;
    }
    int length = 1;
    for (Node p = meet.next; p != meet; p = p.next) {
        length++;
    }
    return length;
}

static void removeLoop(Node head) {
    Node start = loopStart(head);
    if (start == null) {
        return;
    }
    Node last = start;
    while (last.next != start) {
        last = last.next;
    }
    last.next = null;                     // break the loop
}

Node broken = listOf(1, 2, 3, 4, 5);
nodeAt(broken, 4).next = nodeAt(broken, 1);
int length = loopLength(broken);                     // 4
removeLoop(broken);
boolean fixed = hasCycle(broken);                    // false

4. Other Ways to Detect a Cycle

Floyd’s algorithm is the answer most interviewers expect, but it is not the only correct one. A set of visited nodes is the most natural first idea, and it finds the loop start in the same pass.

static Node firstRepeatedNode(Node head) {
    Set<Node> visited = Collections.newSetFromMap(new IdentityHashMap<>());
    for (Node p = head; p != null; p = p.next) {
        if (!visited.add(p)) {
            return p;                     // seen before, so the loop starts here
        }
    }
    return null;
}

Node withSet = listOf(1, 2, 3);
nodeAt(withSet, 2).next = withSet;
int setStart = firstRepeatedNode(withSet).value;     // 1

The set comes from Collections.newSetFromMap() with an IdentityHashMap, so it compares nodes with ==. A plain HashSet works too, as long as the node class does not override equals() to compare values, because in that case two different nodes with the same value would look like a loop.

Approach	Time	Extra memory	Notes
Floyd’s tortoise and hare	O(n)	O(1)	Standard interview answer, finds the start in a second phase
Set of visited nodes	O(n)	O(n)	Simplest code, finds the start in one pass
Brent’s algorithm	O(n)	O(1)	Moves the slow pointer to the fast one at powers of 2, fewer steps on average than Floyd’s
Visited flag in each node	O(n)	One field per node	Changes the node class and needs a reset before the next check
Nested loops from the head	O(n2)	O(1)	Correct but slow, only for tiny lists

For production code with a few thousand nodes, the set version is fine and easier to read. Floyd’s algorithm wins when memory matters or when the nodes are not ours to put into a set, such as values produced by a function.

5. Checking a Manager Chain for Cycles

Say an HR app stores the manager of each employee in a map, and the org chart page walks up the chain from an employee to the CEO. A bad CSV import sets Bob as Cat’s manager and Cat as Bob’s manager, so the walk from Ann never ends. Floyd’s algorithm works on any “next” function, so the same two pointers can check the chain before the page walks it.

static boolean hasManagerCycle(Map<String, String> managerOf, String employee) {
    String slow = employee;
    String fast = employee;
    while (fast != null && managerOf.get(fast) != null) {
        slow = managerOf.get(slow);
        fast = managerOf.get(managerOf.get(fast));
        if (slow != null && slow.equals(fast)) {
            return true;
        }
    }
    return false;
}

Map<String, String> badImport = Map.of("ann", "bob", "bob", "cat", "cat", "bob");
boolean loops = hasManagerCycle(badImport, "ann");                       // true
Map<String, String> goodImport = Map.of("ann", "bob", "bob", "cat");
boolean healthy = hasManagerCycle(goodImport, "ann");                      // false

Here equals() is the right comparison, because each employee ID stands for one person. The import job can reject the file with a clear error instead of leaving a page that never loads.

6. Linked List Loop FAQs

Interviewers often follow up with these questions about pointer speeds and java.util.LinkedList.

6.1. Why does the fast pointer move two nodes and not three?

With two nodes per step, the gap inside the loop shrinks by one node per step, so the pointers always meet. With three nodes per step, the gap shrinks by two, and in a loop of even length with an odd gap the fast pointer jumps over the slow one forever.

6.2. Can a java.util.LinkedList have a loop?

No. The LinkedList class creates and links its nodes itself and never exposes them, so its public methods cannot make a node point back. The puzzle is about lists whose nodes we write ourselves, or about any data where one record points to the next.

6.3. Is Floyd’s algorithm O(n) for every list?

Yes. The slow pointer enters the loop after at most n steps, and the fast pointer catches it before the slow pointer finishes one lap, which is at most n more steps. Each step does a constant amount of work.

6.4. Does the algorithm work on a doubly linked list?

Yes, as long as both pointers follow the next references only. A correct doubly linked list that is not circular has no loop, so a positive result means a bug in the code that links the nodes.

7. Conclusion

Floyd’s tortoise and hare algorithm detects a loop with two pointers, one moving one node and the other two nodes per step. If the fast pointer reaches null, the list ends; if the pointers point to the same node, the list has a loop, and the check needs O(n) time and O(1) memory.

A second phase from the head finds the loop start, and from there we can measure or remove the loop. A set of visited nodes is a simpler alternative when memory is not tight, and the same two-pointer idea checks any chain of links, such as managers or redirects.

8. References

• Cycle detection (Floyd and Brent algorithms)
• IdentityHashMap (Java SE 25 API)
• Collections.newSetFromMap() (Java SE 25 API)
• LinkedList (Java SE 25 API)

Happy Learning !!

Source Code on Github