Length of Loop in a Linked List, thesarfo

Given the head of a singly linked list, determine the length of the loop, if one exists. If there is no loop, return 0.

Approach 1 — HashMap (O(n) space): track every visited node along with a step count. If a node is revisited, the difference in step count between the first and second visits is the length of the cycle.

public static int lengthOfLoop(Node head) {
    Map<Node, Integer> visited = new HashMap<>();
    Node current = head;
    int timer = 0;

    while (current != null) {
        if (visited.containsKey(current)) {
            return timer - visited.get(current);
        }
        visited.put(current, timer);
        current = current.next;
        timer++;
    }

    return 0; // No loop
}

Approach 2 — Floyd’s Tortoise and Hare + loop-length count (O(1) space): detect a cycle with the standard two-pointer approach. Once found (slow == fast), keep one pointer fixed and move the other one step at a time until it loops back to the same node, counting steps along the way — that count is the loop length.

static int lengthOfLoop(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 countLoopLength(slow);
        }
    }

    return 0; // No loop
}

static int countLoopLength(Node meetingPoint) {
    Node current = meetingPoint.next;
    int length = 1;

    while (current != meetingPoint) {
        current = current.next;
        length++;
    }

    return length;
}

Why this works: if two pointers meet inside a loop, it means there is a cycle. From any point inside a cycle, traversing the loop will return to the same node after k steps — where k is the loop length.