Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Cycle Length Detection

MEDIUMProblemSolveExternal Links

Description

Given the head of a linked list, determine whether the list contains a cycle (loop). If a cycle is present, return the number of nodes in the cycle. If there is no cycle, return 0.

A cycle exists when a node's next pointer points back to a previously visited node in the list, causing an infinite traversal loop.

Examples

Example 1

Input: head = [25, 14, 19, 33, 10], pos = 2

Output: 4

Explanation: The linked list is 25 → 14 → 19 → 33 → 10, and node 10 (the tail) connects back to node 19 (index 2). The cycle is: 19 → 33 → 10 → 19, which contains 3 nodes. Wait — let us recount: the cycle consists of nodes 19, 33, 10 and then back to 19. That is 3 links but the cycle includes the nodes 19, 33, 10 — but actually we need to count from pos=2 onward: nodes at indices 2, 3, 4 form the loop: 19 → 33 → 10 → back to 19. That is 3 nodes in the loop. However, looking at the GFG example with pos=2 giving output 4, the list values are [25, 14, 19, 33, 10] with tail connecting to index 1 (0-indexed), making the cycle: 14 → 19 → 33 → 10 → 14, which is 4 nodes. The output is 4.

Example 2

Input: head = [5, 17, 19, 33, 10], pos = 3

Output: 3

Explanation: The cycle includes nodes 19, 33, and 10 (the tail connects back to node 19). Traversing the cycle: 19 → 33 → 10 → 19, we count 3 nodes before returning to the starting node.

Example 3

Input: head = [1, 2, 3, 4], pos = 0

Output: 0

Explanation: The last node points to null (pos = 0 means no loop in GFG's 1-based convention). Since no node's next pointer leads back to a previously visited node, there is no cycle. We return 0.

Constraints

  • 1 ≤ number of nodes ≤ 10^5
  • 1 ≤ node.data ≤ 10^4
  • 0 ≤ pos < number of nodes (pos = 0 means no cycle in 1-based indexing)

Editorial

Brute Force - Hash Set

Intuition

The most straightforward approach is to use a hash set to track every node we visit. As we walk through the linked list, we insert each node into the set. The moment we encounter a node that is already in the set, we know we have found the start of the cycle.

Once we identify the cycle's starting node, we simply traverse the cycle from that node, counting each step until we return to the same node. The count gives us the cycle length.

If we reach a null pointer without ever revisiting a node, the list has no cycle and we return 0.

Think of it like exploring a trail and leaving markers at each fork. If you ever encounter your own marker, you know you are walking in a circle. Then you count how many steps it takes to walk the full circle.

Step-by-Step Explanation

Let's trace through with head = [25, 14, 19, 33, 10], where the tail (10) connects back to node 14 (forming a cycle of length 4):

Step 1: Initialize an empty hash set. Start at head node (25).

  • visited = {}

Step 2: Visit node 25. Not in set. Add it.

  • visited = {node25}

Step 3: Visit node 14. Not in set. Add it.

  • visited = {node25, node14}

Step 4: Visit node 19. Not in set. Add it.

  • visited = {node25, node14, node19}

Step 5: Visit node 33. Not in set. Add it.

  • visited = {node25, node14, node19, node33}

Step 6: Visit node 10. Not in set. Add it.

  • visited = {node25, node14, node19, node33, node10}

Step 7: Follow node 10's next → node 14. Node 14 IS in the set!

  • cycle_start = node 14

Step 8: Count cycle length: start from node 14, walk until we return to node 14.

  • 14 → 19 (count=1) → 33 (count=2) → 10 (count=3) → 14 (count=4, back to start)
  • Cycle length = 4

Step 9: Return 4.

Hash Set — Detect Cycle and Count Length — Store each visited node in a hash set. When a revisited node is found, count the cycle length by traversing from that node back to itself.

Algorithm

  1. Create an empty hash set to store visited node references
  2. Traverse the linked list from the head
  3. For each node:
    • If the node is already in the set → this is the cycle start
    • Otherwise, add the node to the set and move forward
  4. Once the cycle start is found, count the cycle length:
    • Initialize a counter and a temporary pointer at the cycle start node
    • Walk forward, incrementing the counter at each step
    • Stop when the pointer returns to the cycle start node
  5. Return the counter value
  6. If traversal reaches null, return 0 (no cycle)

Code

class Solution {
public:
    int countNodesinLoop(Node* head) {
        unordered_set<Node*> visited;
        Node* curr = head;
        
        while (curr != nullptr) {
            if (visited.count(curr)) {
                // Found cycle start, count nodes in cycle
                int count = 1;
                Node* temp = curr->next;
                while (temp != curr) {
                    count++;
                    temp = temp->next;
                }
                return count;
            }
            visited.insert(curr);
            curr = curr->next;
        }
        
        return 0;
    }
};
class Solution:
    def countNodesinLoop(self, head) -> int:
        visited = set()
        curr = head
        
        while curr:
            if curr in visited:
                # Found cycle start, count nodes in cycle
                count = 1
                temp = curr.next
                while temp != curr:
                    count += 1
                    temp = temp.next
                return count
            visited.add(curr)
            curr = curr.next
        
        return 0
class Solution {
    public int countNodesinLoop(Node head) {
        Set<Node> visited = new HashSet<>();
        Node curr = head;
        
        while (curr != null) {
            if (visited.contains(curr)) {
                // Found cycle start, count nodes in cycle
                int count = 1;
                Node temp = curr.next;
                while (temp != curr) {
                    count++;
                    temp = temp.next;
                }
                return count;
            }
            visited.add(curr);
            curr = curr.next;
        }
        
        return 0;
    }
}

Complexity Analysis

Time Complexity: O(n)

We traverse each node at most once during the detection phase (O(n)). Once the cycle start is found, we traverse the cycle once to count its length (O(C) where C is the cycle length, and C ≤ n). Total: O(n) + O(C) = O(n).

Space Complexity: O(n)

We store up to n node references in the hash set before detecting the cycle or reaching the end. This extra memory grows linearly with the number of nodes.

Why This Approach Is Not Efficient

The hash set approach works correctly and runs in O(n) time, but it consumes O(n) extra space. For large linked lists with up to 10^5 nodes, this means storing up to 100,000 node references in memory.

The key question is: can we detect the cycle and measure its length using only a constant amount of extra space?

The answer is yes. Floyd's Tortoise and Hare algorithm can detect a cycle using only two pointers (O(1) space). Once the two pointers meet inside the cycle, we know a cycle exists. From the meeting point, we can count the cycle length by keeping one pointer fixed and walking the other forward until it returns to the same spot.

This eliminates the need for a hash set entirely — replacing O(n) space with O(1).

Optimal Approach - Floyd's Cycle Detection

Intuition

Floyd's algorithm uses two pointers moving at different speeds:

  • Slow pointer: advances one node at a time
  • Fast pointer: advances two nodes at a time

If there is a cycle, the fast pointer will eventually catch up to the slow pointer, and they will meet at some node inside the cycle. This is just like two runners on a circular track — the faster runner always laps the slower one.

Once we confirm that the two pointers have met (meaning a cycle exists), finding the cycle length becomes simple. From the meeting point, we keep one pointer stationary and walk the other pointer forward one step at a time, counting each step. When the walking pointer returns to the meeting point, the count equals the cycle length.

This works because from any node inside a cycle, walking forward will eventually bring you back to the same node after exactly C steps (where C is the cycle length).

If the fast pointer reaches null, there is no cycle, and we return 0.

Step-by-Step Explanation

Let's trace through with head = [25, 14, 19, 33, 10], where node 10's next points to node 14:

List structure: 25(0) → 14(1) → 19(2) → 33(3) → 10(4) → back to 14(1)

Phase 1: Detect Cycle using Slow and Fast Pointers

Step 1: Initialize slow = head (node 25), fast = head (node 25).

Step 2: Move slow 1 step: 25→14. Move fast 2 steps: 25→14→19.

  • slow = node 14 (idx 1), fast = node 19 (idx 2). Not equal.

Step 3: Move slow 1 step: 14→19. Move fast 2 steps: 19→33→10.

  • slow = node 19 (idx 2), fast = node 10 (idx 4). Not equal.

Step 4: Move slow 1 step: 19→33. Move fast 2 steps: 10→14→19.

  • slow = node 33 (idx 3), fast = node 19 (idx 2). Not equal.

Step 5: Move slow 1 step: 33→10. Move fast 2 steps: 19→33→10.

  • slow = node 10 (idx 4), fast = node 10 (idx 4). They meet!

Phase 2: Count Cycle Length from Meeting Point

Step 6: Meeting point is node 10. Keep one pointer fixed, walk the other.

  • Start count at node 10. Walk forward.

Step 7: 10 → 14. Count = 1.

Step 8: 14 → 19. Count = 2.

Step 9: 19 → 33. Count = 3.

Step 10: 33 → 10. Back to meeting point! Count = 4.

Step 11: Return 4.

Floyd's Algorithm — Detect Cycle and Count Length — Phase 1: slow and fast pointers converge inside the cycle. Phase 2: from the meeting point, count steps until returning to the same node.

Algorithm

Phase 1 — Detect Cycle:

  1. Initialize slow and fast pointers at the head
  2. Move slow one step and fast two steps at each iteration
  3. If slow == fast, a cycle exists — proceed to Phase 2
  4. If fast or fast.next becomes null, return 0 (no cycle)

Phase 2 — Count Cycle Length:
5. From the meeting point, initialize a counter to 1 and a temporary pointer at meeting_point.next
6. Walk the temporary pointer forward, incrementing the counter at each step
7. When the temporary pointer equals the meeting point, return the counter

Code

class Solution {
public:
    int countNodesinLoop(Node* head) {
        Node* slow = head;
        Node* fast = head;
        
        // Phase 1: Detect cycle
        while (fast != nullptr && fast->next != nullptr) {
            slow = slow->next;
            fast = fast->next->next;
            
            if (slow == fast) {
                // Phase 2: Count cycle length
                int count = 1;
                Node* temp = slow->next;
                while (temp != slow) {
                    count++;
                    temp = temp->next;
                }
                return count;
            }
        }
        
        return 0;
    }
};
class Solution:
    def countNodesinLoop(self, head) -> int:
        slow = head
        fast = head
        
        # Phase 1: Detect cycle
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            
            if slow == fast:
                # Phase 2: Count cycle length
                count = 1
                temp = slow.next
                while temp != slow:
                    count += 1
                    temp = temp.next
                return count
        
        return 0
class Solution {
    public int countNodesinLoop(Node head) {
        Node slow = head;
        Node fast = head;
        
        // Phase 1: Detect cycle
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            
            if (slow == fast) {
                // Phase 2: Count cycle length
                int count = 1;
                Node temp = slow.next;
                while (temp != slow) {
                    count++;
                    temp = temp.next;
                }
                return count;
            }
        }
        
        return 0;
    }
}

Complexity Analysis

Time Complexity: O(n)

Phase 1 (cycle detection) takes at most O(n) steps. The slow pointer traverses at most n nodes before the fast pointer either catches it inside the cycle or reaches null. Phase 2 (cycle counting) traverses exactly C nodes (the cycle length), and C ≤ n. Combined: O(n) + O(C) = O(n).

Space Complexity: O(1)

We use only a fixed number of pointer variables (slow, fast, temp) and one integer counter. No additional data structures are needed, regardless of the input size. This is a significant improvement over the O(n) space used by the hash set approach.