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, what is the output when calling findDuplicate([3,1,3,4,2])?

easy

A. 3

B. 1

C. 4

D. 2

Solution

1. Step 1: Trace first phase to find intersection point

   Initialize slow=3, fast=3 (nums[0]=3). Iteration 1: slow=nums[3]=4, fast=nums[nums[3]]=nums[4]=2. Iteration 2: slow=nums[4]=2, fast=nums[nums[2]]=nums[3]=4. Iteration 3: slow=nums[2]=3, fast=nums[nums[4]]=nums[2]=3. They meet at 3.

2. Step 2: Trace second phase to find cycle entrance

   Reset slow=nums[0]=3. Since slow==fast==3, loop ends immediately. Return 3.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Cycle detection returns duplicate 3 correctly [OK]

Hint: Cycle detection returns the duplicate value where pointers meet [OK]

Common Mistakes:

• Confusing slow and fast pointer updates
• Off-by-one errors in indexing
• Returning the wrong pointer value

2. Given the following code for checking if a linked list is a palindrome, what is the final return value when the input list is 1 -> 2 -> 1?

easy

A. Infinite loop

B. False

C. True

D. Raises an exception due to null pointer

Solution

1. Step 1: Trace fast and slow pointers

   For list 1 -> 2 -> 1, slow ends at node with value 2, fast reaches end.

2. Step 2: Reverse second half and compare

   Second half starting at 2 -> 1 is reversed to 1 -> 2. Compare nodes: 1==1, 2==2, all match, so return True.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Palindrome list returns True after correct reversal and comparison [OK]

Hint: Check pointer movement and reversed half comparison carefully [OK]

Common Mistakes:

• Misplacing slow pointer causing wrong half reversal
• Off-by-one error in comparison loop
• Forgetting to advance second_half_start pointer

3. What is the time complexity of Floyd's Tortoise and Hare algorithm for finding the duplicate number in an array of size n+1 with values from 1 to n?

medium

A. O(n) because each pointer moves at most n steps before meeting

B. O(n^2) due to nested pointer updates

C. O(n log n) due to implicit sorting in pointer jumps

D. O(n) but with O(n) extra space for visited nodes

Solution

1. Step 1: Analyze pointer movements

   Slow pointer moves one step at a time, fast pointer moves two steps. They meet within O(n) steps because the cycle length is at most n.

2. Step 2: Confirm no nested loops or extra space

   There are no nested loops; each iteration advances pointers. Space is O(1), so no extra overhead.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Linear time complexity matches pointer traversal count [OK]

Hint: Two pointers meet in linear time, no nested loops [OK]

Common Mistakes:

• Assuming nested loops cause O(n^2)
• Confusing pointer jumps with sorting complexity
• Thinking extra space is used for visited nodes

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

5. What is the space complexity of the stack-based approach to find the nth node from the end in a singly linked list of length n?

medium

A. O(n) because all nodes are stored in the stack

B. O(1) because only a few pointers are used

C. O(n) because recursion stack is used

D. O(log n) due to divide and conquer traversal

Solution

1. Step 1: Identify data structures used

   The stack stores every node in the list, so it holds n nodes.

2. Step 2: Determine space complexity

   Storing all n nodes means O(n) auxiliary space is required.

3. Step 3: Re-examine options

   O(n) because all nodes are stored in the stack states O(n) space which is correct for stack-based approach. O(1) because only a few pointers are used states O(1) which is incorrect for stack-based approach.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Stack size grows linearly with list length [OK]

Hint: Stack stores all nodes, so space is O(n) [OK]

Common Mistakes:

• Assuming constant space due to pointers
• Confusing recursion stack with iterative stack
• Thinking divide and conquer applies here