Linked List Cycle Length

📋

Problem

Imagine you are debugging a network of pipes and want to find if water flows in a loop, and if so, how long that loop is.

Given the head of a singly linked list, determine if the linked list contains a cycle. If a cycle exists, return the length of the cycle (the number of nodes in the cycle). If there is no cycle, return 0.

The number of nodes in the list is in the range [0, 10^5].Node values can be any integer.You must solve the problem using O(1) additional space.

Edge cases: Empty list (head = null) → 0Single node with no cycle → 0Single node with cycle to itself → 1

</>

IDE

def cycle_length(head: Optional[ListNode]) -> int:public int cycleLength(ListNode head)int cycleLength(ListNode* head)function cycleLength(head)

def cycle_length(head):
    # Write your solution here
    pass

class Solution {
    public int cycleLength(ListNode head) {
        // Write your solution here
        return 0;
    }
}

#include <vector>
using namespace std;

int cycleLength(ListNode* head) {
    // Write your solution here
    return 0;
}

function cycleLength(head) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: 0Fails to detect cycle and always returns 0 even when cycle exists.✅ Implement Floyd's cycle detection: move slow by 1 step and fast by 2 steps; detect meeting point.

Wrong: Incorrect cycle length (off by one)Cycle length counting loop stops too early or starts counting from wrong node.✅ After detecting cycle, start counting from meeting node and continue until pointer returns to it.

Wrong: Non-zero for empty or no cycle listsNo null checks or incorrect cycle detection logic causing false positives.✅ Check if fast or fast.next is null to confirm no cycle and return 0.

Wrong: TLE or timeoutUsing hash set or nested loops causing O(n^2) or O(n) space complexity.✅ Use Floyd's cycle detection with two pointers for O(n) time and O(1) space.

✓

Test Cases

Now that basics work, test your code on edge cases like empty and single-node lists.

Next, handle tricky corner cases that expose off-by-one and greedy counting errors.

Finally, test performance on large inputs to ensure your solution is efficient.

t1_01basic

Input{"head":{"vals":[3,2,0,-4],"pos":1}}

Expected3

⏱ Performance - must finish in 2000ms

The cycle is formed by nodes with values 2 -> 0 -> -4 -> back to 2, so the cycle length is 3.

💡 Use fast and slow pointers to detect if a cycle exists.

💡 Once a cycle is detected, keep one pointer fixed and move the other until it meets again to count cycle length.

💡 After detecting cycle, initialize length=1 and move pointer until it returns to start node, incrementing length each step.

Why it failed: Returned wrong cycle length or zero despite cycle existing. Fix: After detecting cycle, count nodes in cycle by moving pointer until it loops back.

✓ Correctly detects cycle and counts its length.

t1_02basic

Input{"head":{"vals":[1,2,3,4,5],"pos":2}}

Expected3

⏱ Performance - must finish in 2000ms

Cycle formed by nodes with values 3 -> 4 -> 5 -> back to 3, cycle length is 3.

💡 Detect cycle using two pointers moving at different speeds.

💡 After detection, count cycle length by traversing cycle nodes once.

💡 Start counting from meeting point and stop when pointer returns to it.

Why it failed: Incorrect cycle length returned or zero despite cycle. Fix: Count cycle nodes by traversing from meeting point until back to it.

✓ Cycle detected and length counted correctly.

t2_01edge

Input{"head":{"vals":[],"pos":-1}}

Expected0

⏱ Performance - must finish in 2000ms

Empty list has no nodes and thus no cycle, so cycle length is 0.

💡 Check if head is null before processing.

💡 If list is empty, return 0 immediately.

💡 No nodes means no cycle, so cycle length must be zero.

Why it failed: Code crashes or returns non-zero for empty list. Fix: Add null check for head at start and return 0 if null.

✓ Correctly handles empty list with no cycle.

t2_02edge

Input{"head":{"vals":[1],"pos":-1}}

Expected0

⏱ Performance - must finish in 2000ms

Single node with no cycle returns 0 since no cycle exists.

💡 Single node with next pointer null means no cycle.

💡 Detect cycle by checking if fast and slow pointers meet; they won't here.

💡 Return 0 if no cycle detected.

Why it failed: Returns non-zero cycle length for single node without cycle. Fix: Ensure cycle detection returns false if no meeting point.

✓ Correctly returns 0 for single node without cycle.

t2_03edge

Input{"head":{"vals":[1],"pos":0}}

Expected1

⏱ Performance - must finish in 2000ms

Single node with cycle to itself forms a cycle of length 1.

💡 Cycle can be a node pointing to itself.

💡 Detect cycle by fast and slow pointers meeting at the same node.

💡 Count cycle length by moving pointer until it returns to start node.

Why it failed: Fails to detect cycle of length 1 or returns 0. Fix: Handle case where node.next points to itself and count length as 1.

✓ Correctly detects and counts cycle length 1.

t3_01corner

Input{"head":{"vals":[1,2,3,4,5,6],"pos":5}}

Expected1

⏱ Performance - must finish in 2000ms

Cycle formed by last node pointing to itself, cycle length is 1.

💡 Check if cycle length counting handles cycle of length 1 correctly.

💡 Ensure counting loop stops only when pointer returns to start node.

💡 Avoid off-by-one errors in cycle length counting.

Why it failed: Cycle length off by one or zero for single-node cycle at end. Fix: Count at least one node and loop until pointer returns to start.

✓ Correctly counts cycle length 1 at list end.

t3_02corner

Input{"head":{"vals":[1,2,3,4,5],"pos":-1}}

Expected0

⏱ Performance - must finish in 2000ms

Long list with no cycle returns 0.

💡 Verify cycle detection does not falsely detect cycles.

💡 Fast pointer reaches null means no cycle.

💡 Return 0 if no cycle detected after traversal.

Why it failed: Returns non-zero cycle length for no cycle list. Fix: Check for null in fast pointer traversal to confirm no cycle.

✓ Correctly returns 0 for no cycle in long list.

t3_03corner

Input{"head":{"vals":[1,2,3,4,5,6,7],"pos":2}}

Expected5

⏱ Performance - must finish in 2000ms

Cycle formed by nodes 3->4->5->6->7->3, cycle length is 5.

💡 Beware of greedy approaches that stop counting too early.

💡 Count all nodes in cycle by traversing until pointer returns to start.

💡 Use slow pointer to detect cycle and then count length precisely.

Why it failed: Cycle length underestimated due to premature counting stop. Fix: Traverse entire cycle until pointer returns to start node.

✓ Correctly counts full cycle length.

t4_01performance

Input{"head":{"vals":[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100],"pos":50}}

Expectednull

⏱ Performance - must finish in 2000ms

List of length 100 with cycle starting at node 51 (0-indexed). Algorithm must run in O(n) time within 2 seconds.

💡 Use Floyd's cycle detection algorithm with two pointers.

💡 Counting cycle length after detection is O(n).

💡 Avoid extra space to meet O(1) space constraint and time limit.

Why it failed: TLE due to using O(n) space or O(n^2) time approach. Fix: Use fast and slow pointers with O(1) space and O(n) time.

✓ Algorithm runs in O(n) time and O(1) space as expected.

Practice

1. Identify the bug in the following Python code for checking if a number is happy. The code attempts to detect cycles using recursion but lacks proper cycle detection.

def isHappy(n: int) -> bool:
    def get_next(number):
        total_sum = 0
        while number > 0:
            digit = number % 10
            total_sum += digit * digit
            number //= 10
        return total_sum

    def helper(num):
        if num == 1:
            return true
        return helper(get_next(num))

    return helper(n)

medium

A. Missing base case for cycle detection causing infinite recursion

B. Incorrect sum of squares calculation in get_next function

C. Returning helper(get_next(num)) without checking if num is 1

D. Not initializing total_sum to zero before summing digits

Solution

1. Step 1: Analyze recursion base cases

   The code only stops recursion if num == 1. It does not detect cycles, so for unhappy numbers it recurses infinitely.

2. Step 2: Identify missing cycle detection

   Without tracking visited numbers or using fast-slow pointers, the recursion never terminates for cycles, causing stack overflow.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Infinite recursion due to missing cycle detection base case [OK]

Hint: Check for cycle detection in recursion to avoid infinite loops [OK]

Common Mistakes:

• Assuming recursion stops at cycles without explicit detection

2. What is the time and space complexity of Floyd's cycle detection algorithm used to find the start of a cycle in a linked list of length n?

medium

A. Time: O(n), Space: O(1)

B. Time: O(n^2), Space: O(1)

C. Time: O(n), Space: O(n)

D. Time: O(n log n), Space: O(1)

Solution

1. Step 1: Analyze time complexity of pointer movements

   Fast pointer moves twice as fast as slow pointer, so they meet in O(n) steps, and locating cycle start also takes O(n) steps, total O(n).

2. Step 2: Analyze space complexity

   Only a fixed number of pointers are used, no extra data structures, so space is O(1).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Linear time and constant space are standard for Floyd's algorithm [OK]

Hint: Two pointers traverse list linearly, no extra space needed [OK]

Common Mistakes:

• Confusing space with hash set approach
• Assuming quadratic time due to nested loops
• Mistaking recursion stack space

3. Consider the following buggy code snippet for reorderList. Which line contains the subtle bug that can cause infinite loops or cycles when traversing the reordered list?

medium

A. Line with 'if left == right or left.next == right:' missing 'right.next = None' termination

B. Line with 'if not right: return' -- base case missing

C. Line with 'if stop: return' -- premature termination

D. Line with 'left = tmp' -- left pointer not updated correctly

Solution

1. Step 1: Identify termination condition

   The code must set right.next = None when left meets right or adjacent to avoid cycles.

2. Step 2: Locate missing termination

   The commented line misses 'right.next = None', causing the list to form cycles.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Missing termination causes infinite traversal [OK]

Hint: Always terminate reordered list with null to avoid cycles [OK]

Common Mistakes:

• Forgetting to set right.next = null
• Misplacing stop flag
• Incorrect pointer updates

4. Suppose the problem is modified so that the array elements can be zero, representing no movement, and cycles of length 1 (self-loop) are now considered valid. Which modification to the original fast and slow pointer algorithm correctly handles this variant?

hard

A. Remove the check that breaks when slow == next_index(slow), allowing single-element loops to return True.

B. Add a condition to skip zeros in the outer loop and treat zero jumps as invalid for cycles.

C. Modify the direction check to allow zero as both positive and negative direction to include zero jumps.

D. Use a visited set to track indices and return True if any index is revisited, ignoring direction.

Solution

1. Step 1: Understand new problem constraints

   Zero jumps are allowed and single-element loops are valid cycles.

2. Step 2: Identify necessary algorithm change

   The original code breaks when slow == next_index(slow) to exclude single-element loops; removing this check allows detecting single-element cycles.

3. Step 3: Confirm direction and zero handling

   Zeros represent no movement; allowing them means direction check must still be consistent, but zero jumps can form valid cycles.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Removing single-element loop break correctly detects new valid cycles [OK]

Hint: Allow single-element loops by removing cycle length >1 check [OK]

Common Mistakes:

• Skipping zeros entirely
• Treating zero as both directions
• Ignoring direction consistency

5. Suppose the problem is modified so that after deleting N nodes, the deleted nodes can be reinserted later in the list (i.e., nodes can be reused). Which of the following changes to the algorithm is necessary to correctly handle this variant?

hard

A. Use a recursive approach to backtrack and reinsert deleted nodes at correct positions.

B. Maintain a separate data structure to store deleted nodes and reinsert them after traversal.

C. Modify the iterative approach to skip M nodes, delete N nodes, and immediately reattach deleted nodes after the next M nodes.

D. No change needed; the original iterative approach already supports node reuse.

Solution

1. Step 1: Understand node reuse requirement

   Deleted nodes must be preserved and reinserted later, so they cannot be simply discarded by pointer reassignment.

2. Step 2: Evaluate algorithm changes

   The original approach loses references to deleted nodes. To reuse, store deleted nodes externally and reinsert after traversal or at correct positions.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Maintaining deleted nodes separately enables controlled reinsertion [OK]

Hint: Reusing nodes requires storing them, not discarding pointers [OK]

Common Mistakes:

• Assuming original approach supports reuse
• Trying to reattach nodes immediately without storage
• Using recursion unnecessarily