Linked List Cycle Detection

📋

Problem

Imagine you are debugging a network of pipes where water flows in loops. Detecting if water can endlessly circulate in a loop is like detecting a cycle in a linked list.

Given the head of a singly linked list, determine if the linked list has a cycle in it. Return true if there is a cycle, otherwise return false.

The number of nodes in the list is in the range [0, 10^5].Node values are arbitrary and do not affect cycle detection.You must solve the problem using O(1) (constant) memory if possible.

Edge cases: Empty list (head = null) → falseSingle node with no cycle → falseSingle node with cycle to itself → true

</>

IDE

def hasCycle(head: Optional[ListNode]) -> bool:public boolean hasCycle(ListNode head)bool hasCycle(ListNode* head)function hasCycle(head)

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

class Solution {
    public boolean hasCycle(ListNode head) {
        // Write your solution here
        return false;
    }
}

#include <vector>
using namespace std;

bool hasCycle(ListNode* head) {
    // Write your solution here
    return false;
}

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

Common Bugs to Avoid

Wrong: falseDid not detect cycle because fast pointer or slow pointer movement logic is incorrect or missing meeting condition.✅ Ensure fast pointer moves two steps and slow pointer moves one step; check if they meet to detect cycle.

Wrong: trueIncorrectly returning true when no cycle exists, possibly missing null checks for fast pointer or fast.next.✅ Add null checks before moving fast pointer; return false if fast pointer or fast.next is null.

Wrong: falseFails on single node cycle where node points to itself; fast pointer movement or meeting condition not handled properly.✅ Handle single node cycle by allowing fast pointer to move two steps and check meeting with slow pointer.

Wrong: TLEUsing nested loops or hash sets causing O(n^2) or O(n) space complexity instead of O(1) space Floyd's algorithm.✅ Implement Floyd's cycle detection with two pointers moving at different speeds for O(n) time and O(1) space.

✓

Test Cases

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

Next, handle tricky cases with cycles at various positions and small lists.

Finally, optimize your solution to handle large inputs efficiently.

t1_01basic

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

Expectedtrue

⏱ Performance - must finish in 2000ms

The linked list contains a cycle because the last node points back to the second node (index 1).

💡 Use two pointers moving at different speeds to detect cycles.

💡 Check if fast and slow pointers ever meet inside the list.

💡 Return true if pointers meet; otherwise false if fast pointer reaches null.

Why it failed: Returned false despite cycle present. Likely forgot to check fast pointer's next or did not detect pointer meeting. Fix by ensuring fast pointer moves two steps and compare with slow pointer each iteration.

✓ Correctly detected cycle using fast and slow pointers.

t1_02basic

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

Expectedfalse

⏱ Performance - must finish in 2000ms

The linked list has no cycle; tail node points to null.

💡 If fast pointer reaches null, no cycle exists.

💡 Ensure to check fast pointer and fast.next before moving fast pointer.

💡 Return false if fast pointer or fast.next is null during traversal.

Why it failed: Returned true incorrectly. Possibly did not check for fast pointer reaching null. Fix by adding null checks before moving fast pointer.

✓ Correctly identified no cycle in the list.

t2_01edge

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

Expectedfalse

⏱ Performance - must finish in 2000ms

Empty list has no nodes and thus no cycle.

💡 Check if head is null at the start.

💡 If head is null, return false immediately.

💡 No traversal needed for empty list.

Why it failed: Returned true on empty list. Fix by adding initial null check for head before traversal.

✓ Correctly handled empty list with no cycle.

t2_02edge

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

Expectedfalse

⏱ Performance - must finish in 2000ms

Single node with no cycle points to null.

💡 Single node's next is null means no cycle.

💡 Check fast pointer and fast.next before moving.

💡 Return false if fast pointer reaches null.

Why it failed: Returned true incorrectly for single node no cycle. Fix by checking fast pointer's next before advancing.

✓ Correctly identified no cycle in single node list.

t2_03edge

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

Expectedtrue

⏱ Performance - must finish in 2000ms

Single node with cycle to itself forms a loop.

💡 Cycle can be a node pointing to itself.

💡 Fast and slow pointers will meet immediately.

💡 Return true if pointers meet at any node.

Why it failed: Returned false for single node cycle. Fix by ensuring fast pointer moves two steps and check for meeting with slow pointer.

✓ Correctly detected cycle in single node pointing to itself.

t3_01corner

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

Expectedfalse

⏱ Performance - must finish in 2000ms

Two nodes with no cycle; tail points to null.

💡 Check that fast pointer and fast.next are not null before moving.

💡 Avoid null pointer dereference in two-node list.

💡 Return false if fast pointer reaches null.

Why it failed: Returned true incorrectly for two nodes no cycle. Fix by adding null checks before advancing fast pointer.

✓ Correctly identified no cycle in two-node list.

t3_02corner

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

Expectedtrue

⏱ Performance - must finish in 2000ms

Two nodes with cycle where tail points back to head.

💡 Cycle can form by last node pointing to any previous node.

💡 Fast pointer moves two steps, slow moves one step.

💡 Pointers will meet inside the cycle.

Why it failed: Returned false for two-node cycle. Fix by ensuring fast pointer moves two steps and check for meeting with slow pointer.

✓ Correctly detected cycle in two-node list with tail pointing to head.

t3_03corner

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

Expectedtrue

⏱ Performance - must finish in 2000ms

Cycle starts at node index 2 in a longer list.

💡 Cycle can start anywhere, not just head or tail.

💡 Fast pointer may lap slow pointer multiple times.

💡 Detect cycle by checking pointer equality during traversal.

Why it failed: Returned false for cycle starting mid-list. Fix by continuing traversal until pointers meet or fast pointer reaches null.

✓ Correctly detected cycle starting at middle node.

t4_01performance

Input{"head":{"nodes":[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

Large list with 100 nodes and a cycle starting at node 50. Algorithm must run in O(n) time within 2 seconds.

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

💡 Avoid extra memory usage to meet O(1) space constraint.

💡 Ensure fast pointer moves two steps and slow pointer one step each iteration.

Why it failed: Algorithm timed out due to O(n^2) or higher complexity. Fix by implementing Floyd's cycle detection with O(n) time and O(1) space.

✓ Algorithm runs efficiently in O(n) time and O(1) space for large input.

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. 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

3. 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

4. Identify the bug in the following code snippet for detecting and returning the cycle length in a linked list.

medium

A. Line 11: The length counting loop should start with length = 0 instead of 1.

B. Line 6: slow pointer should move two steps instead of one.

C. Line 7: fast pointer should move one step instead of two.

D. Line 4: The condition should check both fast and fast.next to avoid null pointer errors.

Solution

1. Step 1: Check loop condition for pointer safety

   The loop condition only checks if fast is not null, but fast.next may be null causing runtime error on fast.next.next.

2. Step 2: Confirm other lines are correct

   Slow moves one step, fast moves two steps correctly; length counting starts at 1 correctly.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Missing fast.next check causes null pointer dereference [OK]

Hint: Always check fast and fast.next before advancing fast by two steps [OK]

Common Mistakes:

• Forgetting fast.next check
• Off-by-one in length counting
• Swapping slow and fast pointer steps

5. Consider the following code snippet for palindrome check. Which line contains a subtle bug that can cause incorrect results on odd-length lists?

medium

A. Line where second_half_start is assigned by reversing slow

B. Line where slow pointer is advanced in the while loop

C. Line where first_half_start and second_half_start values are compared

D. Line where fast pointer is advanced in the while loop

Solution

1. Step 1: Understand midpoint selection

   For odd-length lists, slow points to the middle node, which should be skipped before reversal.

2. Step 2: Identify bug in reversal start

   Reversing from slow includes the middle node, causing mismatch in comparison.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Correct approach skips middle node before reversal on odd-length lists [OK]

Hint: Check if middle node is excluded before reversing second half [OK]

Common Mistakes:

• Reversing from slow without skipping middle node
• Incorrect fast/slow pointer advancement
• Not handling odd-length lists separately