Linked List Cycle Detection

▶

Steps

setup

Initialize current pointer to head

Set the traversal pointer 'current' to the head of the linked list to start checking nodes from the beginning.

💡 Starting at the head ensures we check every node in order to detect a cycle if it exists.

Line:

current = head

💡 Traversal begins at the first node, preparing to inspect each node's visited status.

compare

Check if current node is visited

Inspect the 'visited' flag of the current node (value 3). Since it is not visited, continue traversal.

💡 Checking visited status prevents infinite loops by detecting if we've seen this node before.

Line:

if current.visited:

💡 No cycle detected yet; this node is new to the traversal.

insert

Mark current node as visited

Mark the current node (value 3) as visited to record that it has been checked.

💡 Marking nodes prevents revisiting the same node and helps detect cycles.

Line:

current.visited = True

💡 This node is now flagged, so if encountered again, a cycle is detected.

advance

Advance current pointer to next node

Move the 'current' pointer from node with value 3 to the next node with value 2.

💡 Advancing the pointer allows the algorithm to check the next node in the list.

Line:

current = current.next

💡 Traversal proceeds sequentially through the list nodes.

compare

Check if current node is visited

Check if the current node (value 2) has been visited before. It has not, so continue.

💡 Each node must be checked to detect if a cycle exists by revisiting nodes.

Line:

if current.visited:

💡 No cycle detected at this node; traversal continues.

insert

Mark current node as visited

Mark the current node (value 2) as visited to record it has been checked.

💡 Marking nodes prevents infinite loops by identifying revisits.

Line:

current.visited = True

💡 This node is now flagged as visited for future cycle detection.

advance

Advance current pointer to next node

Move the 'current' pointer from node with value 2 to the next node with value 0.

💡 Advancing pointer moves traversal forward to check the next node.

Line:

current = current.next

💡 Traversal continues through the list nodes sequentially.

compare

Check if current node is visited

Check if the current node (value 0) has been visited. It has not, so continue.

💡 Each node must be checked to detect cycles by revisiting nodes.

Line:

if current.visited:

💡 No cycle detected at this node; traversal continues.

insert

Mark current node as visited

Mark the current node (value 0) as visited to record it has been checked.

💡 Marking nodes prevents infinite loops by identifying revisits.

Line:

current.visited = True

💡 This node is now flagged as visited for future cycle detection.

advance

Advance current pointer to next node

Move the 'current' pointer from node with value 0 to the next node with value -4.

💡 Advancing pointer moves traversal forward to check the next node.

Line:

current = current.next

💡 Traversal continues through the list nodes sequentially.

compare

Check if current node is visited

Check if the current node (value -4) has been visited. It has not, so continue.

💡 Each node must be checked to detect cycles by revisiting nodes.

Line:

if current.visited:

💡 No cycle detected at this node; traversal continues.

insert

Mark current node as visited

Mark the current node (value -4) as visited to record it has been checked.

💡 Marking nodes prevents infinite loops by identifying revisits.

Line:

current.visited = True

💡 This node is now flagged as visited for future cycle detection.

advance

Advance current pointer to next node (cycle)

Move the 'current' pointer from node with value -4 to the next node with value 2, which creates a cycle.

💡 Advancing pointer into a previously visited node reveals the cycle.

Line:

current = current.next

💡 Traversal reaches a node already visited, indicating a cycle.

compare

Check if current node is visited (cycle detected)

Check if the current node (value 2) has been visited. It has been visited before, so a cycle is detected.

💡 Detecting a visited node again confirms the presence of a cycle.

Line:

if current.visited:

💡 The algorithm successfully detects the cycle by revisiting a marked node.

prune

Return true - cycle detected

Since a cycle is detected, the function returns true, ending the traversal.

💡 Returning true confirms the presence of a cycle in the linked list.

Line:

return True

💡 The algorithm terminates early upon cycle detection, optimizing performance.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
        self.visited = False

def hasCycle(head):
    current = head  # STEP 1
    while current:
        if current.visited:  # STEP 2,5,8,11,14
            return True  # STEP 15
        current.visited = True  # STEP 3,6,9,12
        current = current.next  # STEP 4,7,10,13
    return False

if __name__ == '__main__':
    node1 = ListNode(3)
    node2 = ListNode(2)
    node3 = ListNode(0)
    node4 = ListNode(-4)
    node1.next = node2
    node2.next = node3
    node3.next = node4
    node4.next = node2  # cycle
    print(hasCycle(node1))  # Output: True

📊

Linked List Cycle Detection - Watch the Algorithm Execute, Step by Step

Watching this step-by-step traversal and marking process helps you understand how cycle detection works without extra memory or complex pointer manipulations.

advance

3

→

2

→

0

→

-4

compare

3

→

2

→

0

→

-4

insert

3

→

2

→

0

→

-4

advance

3

→

2

→

0

→

-4

compare

3

→

2

→

0

→

-4

insert

3

→

2

→

0

→

-4

advance

3

→

2

→

0

→

-4

compare

3

→

2

→

0

→

-4

insert

3

→

2

→

0

→

-4

advance

3

→

2

→

0

→

-4

compare

3

→

2

→

0

→

-4

insert

3

→

2

→

0

→

-4

advance

3

→

2

→

0

→

-4

compare

3

→

2

→

0

→

-4

Result: true

prune

3

→

2

→

0

→

-4

Result: true

Key Takeaways

✓ Marking nodes as visited allows cycle detection without extra data structures.

This insight is hard to see from code alone because the visited flag is implicit and not a standard approach.

✓ Traversal stops immediately upon detecting a visited node, optimizing performance.

Understanding early termination is easier when watching the pointer movement and visited checks visually.

✓ The cycle is detected exactly when the traversal pointer revisits a previously marked node.

Seeing the pointer revisit a node clarifies why the algorithm returns true at that moment.

Practice

1. You are given a singly linked list and need to determine the length of a cycle if one exists. Which approach guarantees an optimal solution with O(n) time and O(1) space complexity?

easy

A. Use dynamic programming to store cycle lengths for sublists and combine results.

B. Use a hash set to store visited nodes and count cycle length upon revisiting a node.

C. Use two pointers moving at different speeds to detect the cycle and then count its length by traversing the cycle once.

D. Use a recursive depth-first search to detect cycles and count their lengths.

Solution

1. Step 1: Understand the problem constraints

   The problem requires detecting a cycle and counting its length efficiently in a linked list.

2. Step 2: Evaluate approaches for time and space complexity

   Using two pointers (fast and slow) allows cycle detection in O(n) time and O(1) space, then counting the cycle length by traversing the cycle once is optimal.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Fast-slow pointer approach is classic for cycle detection with constant space [OK]

Hint: Fast-slow pointers detect cycles in O(1) space [OK]

Common Mistakes:

• Believing hash sets are optimal due to extra space
• Confusing DP with cycle detection
• Using recursion unnecessarily

2. Consider the following buggy code snippet for detecting a circular array loop. Which line contains the subtle bug that causes incorrect detection of single-element loops as valid cycles?

medium

A. Line with 'if nums[i] == 0: continue' - skipping zeros prematurely

B. Line with 'if slow == fast: return True' - missing check for single-element loop

C. Line with 'direction = nums[i] > 0' - direction assignment incorrect

D. Line with 'nums[slow] = 0' - zeroing visited elements too early

Solution

1. Step 1: Identify where single-element loops are checked

   The original code breaks if slow == next_index(slow) to avoid single-element loops.

2. Step 2: Locate missing check

   The buggy code returns True immediately when slow == fast without verifying cycle length.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Missing single-element loop check causes false positives [OK]

Hint: Check cycle length before returning True to avoid single-element loops [OK]

Common Mistakes:

• Returning True immediately on pointer meet
• Ignoring direction consistency
• Incorrectly zeroing elements

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

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

5. Suppose the linked list nodes can be reused multiple times in cycles (i.e., cycles can overlap or nest). Which modification to the fast-slow pointer approach correctly detects and counts the length of the first cycle encountered?

hard

A. Use a hash set to track visited nodes to detect cycles and count length, since fast-slow pointers fail with overlapping cycles.

B. Modify the fast pointer to move three steps at a time to detect overlapping cycles faster.

C. Run the fast-slow pointer detection multiple times from different starting points to find all cycles.

D. Use fast-slow pointers as usual; overlapping cycles do not affect detection of the first cycle.

Solution

1. Step 1: Understand overlapping cycles scenario

   Overlapping or nested cycles mean fast-slow pointers may not reliably detect all cycles or count lengths correctly.

2. Step 2: Evaluate approaches for correctness

   Using a hash set tracks all visited nodes, ensuring detection of any cycle and accurate length counting despite overlaps.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Hash set approach handles complex cycle structures correctly [OK]

Hint: Fast-slow pointers detect only simple cycles reliably [OK]

Common Mistakes:

• Assuming fast-slow pointers handle overlapping cycles
• Increasing fast pointer speed breaks correctness
• Multiple runs of fast-slow pointers are inefficient and incomplete