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. Given the following code snippet for detecting a circular array loop, what is the return value when the input is nums = [2, -1, 1, 2, 2]?

easy

A. True

B. False

C. Raises an IndexError

D. Infinite loop

Solution

1. Step 1: Trace first iteration starting at index 0

   nums[0]=2 (positive), direction is forward. slow and fast start at 0.

2. Step 2: Move slow and fast pointers

   slow moves to index (0+2)%5=2, fast moves two steps: first to 2, then to (2+1)%5=3. Both nums[2] and nums[3] are positive, direction consistent.

3. Step 3: Next iteration

   slow moves to (2+1)%5=3, fast moves two steps: from 3 to (3+2)%5=0, then from 0 to (0+2)%5=2. slow=3, fast=2, not equal yet.

4. Step 4: Next iteration

   slow moves to (3+2)%5=0, fast moves two steps: from 2 to (2+1)%5=3, then from 3 to (3+2)%5=0. slow=0, fast=0, pointers meet.

5. Step 5: Check cycle length

   Check if slow == next_index(slow): next_index(0) = 2, not equal, so cycle length > 1.

6. Final Answer:

   Option A -> Option A

7. Quick Check:

   Cycle detected with consistent direction and length > 1 [OK]

Hint: Pointers meet at index 0 with valid cycle -> returns True [OK]

Common Mistakes:

• Confusing slow and fast pointer positions
• Ignoring direction check
• Mistaking single-element loop as valid

2. You need to find the value of the node that is n positions from the end in a singly linked list. Which approach guarantees a single-pass solution with O(n) time complexity and O(1) extra space?

easy

A. Using a stack to store all nodes and then popping n times to get the target node.

B. Using two pointers where the fast pointer advances n steps ahead, then both move until fast reaches the end.

C. Calculating the length of the list first, then traversing again to the (length - n)th node.

D. Using a recursive function to traverse to the end and count back to the nth node.

Solution

1. Step 1: Understand the problem constraints

   The goal is to find the nth node from the end in a single pass with minimal extra space.

2. Step 2: Evaluate approaches

   Using two pointers with the fast pointer n steps ahead allows the slow pointer to land exactly on the target node when fast reaches the end, achieving O(n) time and O(1) space.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Two-pointer technique is classic for single-pass linked list problems [OK]

Hint: Two pointers with gap n solve in one pass [OK]

Common Mistakes:

• Confusing stack approach as single pass
• Using two passes instead of one
• Assuming recursion is O(1) space

3. What is the time complexity of the optimized fast-slow pointer algorithm for detecting a cycle in a circular array of length n, where each element can be positive or negative steps? Assume the algorithm marks visited elements in-place to avoid repeated work.

medium

A. O(n) because each element is visited at most twice due to in-place marking

B. O(n) average but O(n^2) worst-case if cycles overlap heavily

C. O(n log n) due to repeated modulo operations and pointer jumps

D. O(n^2) because each element can be visited multiple times during cycle checks

Solution

1. Step 1: Analyze outer and inner loops

   Each index is processed once in the outer loop; inner while loop visits elements until cycle or zero marking.

2. Step 2: Check effect of in-place marking

   Marking visited elements as zero prevents revisiting, ensuring total visits across all iterations is O(n).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   In-place marking guarantees linear time complexity [OK]

Hint: In-place marking -> each element visited once [OK]

Common Mistakes:

• Assuming repeated visits cause O(n²)
• Ignoring marking effect
• Confusing modulo cost as log factor

4. What is the time complexity of the optimal Happy Number detection algorithm that uses a known cycle set and repeatedly computes the sum of squares of digits until it reaches 1 or a cycle number? Assume n is the input number and k is the number of iterations until termination.

medium

A. O(n) because each digit is processed once per iteration

B. O(k * log n) because each iteration processes digits proportional to log n and there are k iterations

C. O(k * n) because sum of squares depends on n itself

D. O(k) because the cycle detection set lookup is constant time and digits are fixed length

Solution

1. Step 1: Identify cost per iteration

   Each iteration computes sum of squares of digits. Number of digits in n is proportional to log n, so each iteration is O(log n).

2. Step 2: Multiply by number of iterations k

   The process repeats k times until reaching 1 or cycle. Total time is O(k * log n).

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Sum of digits per iteration is log n, repeated k times -> O(k * log n) [OK]

Hint: Sum of digits cost is O(log n), not O(n) [OK]

Common Mistakes:

• Confusing n with number of digits, assuming O(n) per iteration

5. If the linked list nodes can be reused multiple times (i.e., the list is cyclic or can be traversed repeatedly), which modification is necessary to the optimal palindrome check algorithm?

hard

A. No modification needed; the current algorithm works as is.

B. Use a stack to store first half values instead of reversing to avoid modifying the list.

C. Convert the list to an array to handle multiple traversals safely.

D. Restore the reversed second half to original order after comparison to preserve list structure.

Solution

1. Step 1: Understand reuse implications

   If nodes are reused or list is cyclic, modifying it breaks future traversals.

2. Step 2: Restore list after palindrome check

   Reversing second half in-place must be undone to preserve original list structure.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Restoring reversed half ensures list integrity for reuse [OK]

Hint: Always restore list after in-place reversal if list is reused [OK]

Common Mistakes:

• Ignoring list restoration causing side effects
• Switching to stack approach unnecessarily increasing space
• Assuming array conversion is always better