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. Given the following Python code for reorderList and the input list 1->2->3->4, what is the value of the node pointed to by left after the first merge step in the recursion unwinding?

easy

A. Node with value 3

B. Node with value 2

C. Node with value 4

D. Node with value 1

Solution

1. Step 1: Trace recursion to the end

   Recursion reaches right = None, then unwinds from node 4 back to node 1.

2. Step 2: First merge step during unwinding

   At right=4, left=1, tmp=left.next=2; left.next=4; 4.next=2; left=2 after merge.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   After first merge, left points to node with value 2 [OK]

Hint: left moves forward after merging right node [OK]

Common Mistakes:

• Confusing left pointer update
• Off-by-one in recursion unwind
• Misreading next pointer assignments

2. What is the time complexity of the optimized iterative approach for deleting N nodes after skipping M nodes in a singly linked list of length n? Assume M and N are constants.

medium

A. O(n)

B. O(n * (M + N))

C. O(n^2)

D. O(n + M + N)

Solution

1. Step 1: Identify loop behavior

   The algorithm traverses the list once, moving forward by skipping M nodes and deleting N nodes repeatedly.

2. Step 2: Analyze complexity

   Since M and N are constants, each iteration moves forward by at least M+N nodes, so total steps proportional to n.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Single pass traversal yields O(n) time complexity [OK]

Hint: Constant M, N means linear traversal dominates [OK]

Common Mistakes:

• Mistaking nested loops causing O(n*(M+N))
• Assuming quadratic due to inner loops
• Ignoring that M and N are constants

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

5. Suppose the array can contain multiple duplicates and some numbers appear more than twice. Which modification to Floyd's cycle detection algorithm correctly finds any duplicate number?

hard

A. No modification needed; Floyd's algorithm works regardless of duplicate count

B. Use a hash set to track visited numbers instead of cycle detection

C. Run Floyd's algorithm multiple times, removing found duplicates each time

D. Floyd's algorithm still works because the cycle corresponds to any duplicate, even if repeated

Solution

1. Step 1: Understand Floyd's algorithm behavior with multiple duplicates

   The cycle in the array corresponds to the repeated number's indices. Even if duplicates appear multiple times, the cycle exists and Floyd's algorithm detects its entrance.

2. Step 2: Confirm no need for multiple runs or extra data structures

   Floyd's algorithm finds one duplicate per run. It does not require modification to detect duplicates repeated more than twice.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Cycle detection finds the cycle entrance regardless of duplicate frequency [OK]

Hint: Cycle entrance corresponds to duplicate regardless of count [OK]

Common Mistakes:

• Assuming Floyd's algorithm only works if duplicate appears twice
• Thinking multiple runs or extra space are needed
• Confusing cycle detection with hash-based methods