Topics › Linked List › Medium Problems of LL

Length of loop in LL

Medium TUF ID 623 A2Z

Java source ↗ Edit this article ↗

Jump to code: Brute Better Optimal

Problem

You are given the head of a singly linked list that may contain a loop, meaning the last node’s next points back to an earlier node. Return the number of nodes on the loop. If the list has no loop, return 0. The list must not be modified.

Only pointer structure counts; equal values in different nodes do not make a loop. In the tests, a loop is described by the index pos that the tail points back to (-1 for none), so the expected length is n - pos.

Constraints: 0 ≤ n ≤ 10^5 nodes, values fit in a 32-bit signed integer.

static class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

Example 1

head = 1 -> 2 -> 3 -> 4 -> 5,  tail points to index 2 (the node 3)
answer = 3                    // the loop is 3 -> 4 -> 5 -> 3

Example 2

head = 1 -> 2 -> 3 -> 4 -> 5,  tail points to index 0
answer = 5                    // the entire list is the loop

Example 3

head = 1 -> 2 -> 3,  no loop
answer = 0

Approach 1: Brute force, hash map with step numbers

Intuition. While walking the list, number the steps 0, 1, 2, ... and record, for every node, the step at which it was first visited. The first time we land on a node that already has a step number, we have gone exactly once around the loop since that first visit. So currentStep - firstSeenStep is the number of nodes on the loop.

For example, with the loop 3 -> 4 -> 5 -> 3 after 1 -> 2: node 3 is first seen at step 2, and we return to it at step 5. 5 - 2 = 3 nodes were visited in between (3, 4, 5), which is the loop length.

Algorithm.

1. Create an empty HashMap<ListNode, Integer> and set step = 0.
2. Walk from head. For each node:
   • If the map already has it, return step - map.get(node).
   • Otherwise store map.put(node, step) and increase step.
3. If the walk reaches null, return 0.

static int bruteForce(ListNode head) {
    Map<ListNode, Integer> firstSeen = new HashMap<>();
    int step = 0;
    for (ListNode t = head; t != null; t = t.next, step++) {
        Integer earlier = firstSeen.get(t);
        if (earlier != null) return step - earlier;   // nodes visited between the two visits form the loop
        firstSeen.put(t, step);
    }
    return 0;
}

Complexity. Time O(n): at most n + 1 visits, each with an O(1) average map operation. Space O(n): one entry per node on the path.

The map keys are node references; ListNode does not override equals or hashCode, so equal values in different nodes are correctly treated as different keys.

Approach 2: Optimal, detect with Floyd then walk one lap

Intuition. Floyd’s tortoise and hare (one pointer moving one node per step, the other two) meets the two pointers on the loop if a loop exists; if fast reaches null, there is none. The meeting node might not be the loop’s start, but that does not matter: every node on the loop is equally good as a starting line for a lap. Hold the meeting node fixed, move a second pointer forward from it, and count steps until it comes back. That count is the loop length.

Why do the pointers meet at all? Once both are on the loop, fast gains exactly one node on slow per step, so the gap between them decreases by one each step and must hit zero within one lap. No node can be skipped.

Algorithm.

1. Set slow = head, fast = head.
2. While fast and fast.next are non-null: slow = slow.next, fast = fast.next.next. If slow == fast, go to step 3.
3. Starting from the meeting node, set length = 1 and move a pointer t = meeting.next; while t != meeting, advance t and increase length. Return length.
4. If the first loop exited because fast hit null, return 0.

static int optimal(ListNode head) {
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) return loopLength(slow);   // the meeting node is somewhere on the loop
    }
    return 0;
}

The counting step is its own small method so that it reads clearly:

static int loopLength(ListNode onLoop) {
    int length = 1;
    for (ListNode t = onLoop.next; t != onLoop; t = t.next) length++;
    return length;
}

Dry run on 1 -> 2 -> 3 -> 4 -> 5 with the tail pointing to 3:

Complexity. Time O(n): detection is linear (at most the tail length plus one lap), and the counting lap is exactly C ≤ n steps. Space O(1): two or three pointers and a counter.

Both approaches are tested in the Java file against n - pos for the same inputs, including a 100 000-node list with a loop of 75 000 nodes.

Edge cases and pitfalls

• No loop. Return 0, not -1 or 1. The fast pointer reaching null is the only signal; never start counting unless the pointers actually met.
• Self-loop. A node whose next is itself has loop length 1. The counting method starts length at 1 and t = meeting.next equals meeting immediately, so the loop body never runs.
• Whole list is the loop. Tail pointing to the head gives length n.
• Empty list. fast is null on entry; return 0.
• Counting from the wrong anchor. Count from the meeting node back to the meeting node. Counting from head, or from the meeting node to the loop start, gives wrong answers.
• Off-by-one in the lap. Start the count at 1 for the meeting node itself and count every other node once as t passes it. Starting at 0 and comparing after moving also works, but mixing the two conventions produces C - 1 or C + 1.
• Comparing values. t != onLoop and slow == fast are reference comparisons. The tests include a loop on a list where every value is 9.

Related problems

• Detect a loop in LL is the detection phase on its own.
• Find the starting point in LL locates the first node of the loop after the same meeting.
• Find the length of the Linked List is the loop-free counting problem.
• Middle of a LinkedList [TortoiseHare Method] uses slow and fast pointers to find a position instead of a loop.