Linked List Cycle II - Start of Cycle

▶

Steps

setup

Initialize pointers slow and fast at head

Both slow and fast pointers start at the head node with value 3. This sets up the initial state for cycle detection.

💡 Starting both pointers at head is essential because Floyd’s algorithm relies on their relative speeds from the same start.

Line:

slow = fast = head

💡 Both pointers begin together, ready to traverse the list at different speeds.

fill_cells

Move slow one step forward

Slow pointer moves from node 3 to node 2, advancing one step as per Floyd’s algorithm.

💡 Slow pointer moves at normal speed, one node at a time, to eventually meet fast if a cycle exists.

Line:

slow = slow.next

💡 Slow pointer progresses steadily through the list.

fill_cells

Move fast two steps forward

Fast pointer moves from node 3 to node 0 by jumping two nodes ahead.

💡 Fast pointer moves twice as fast to catch up with slow inside the cycle if one exists.

Line:

fast = fast.next.next

💡 Fast pointer covers more ground quickly, increasing chance of meeting slow.

fill_cells

Move slow one step forward

Slow pointer moves from node 2 to node 0, continuing its steady pace.

💡 Slow pointer keeps moving one node at a time to eventually meet fast inside the cycle.

Line:

slow = slow.next

💡 Slow pointer is closing in on fast pointer’s position.

fill_cells

Move fast two steps forward

Fast pointer moves from node 0 to node 2 by jumping two nodes ahead, entering the cycle.

💡 Fast pointer’s double step allows it to catch up with slow inside the cycle.

Line:

fast = fast.next.next

💡 Fast pointer is now inside the cycle, same as slow.

fill_cells

Move slow one step forward

Slow pointer moves from node 0 to node -4, continuing inside the cycle.

💡 Slow pointer continues moving steadily inside the cycle to eventually meet fast.

Line:

slow = slow.next

💡 Slow pointer is progressing through the cycle nodes.

fill_cells

Move fast two steps forward

Fast pointer moves from node 2 to node -4 by jumping two nodes ahead inside the cycle.

💡 Fast pointer moves quickly inside the cycle to meet slow.

Line:

fast = fast.next.next

💡 Fast pointer is closing the gap with slow inside the cycle.

compare

Pointers meet inside the cycle

Slow and fast pointers meet at node with value -4, confirming a cycle exists.

💡 Meeting inside the cycle proves the list has a cycle and identifies a node within it.

Line:

if slow == fast: break

💡 Cycle detection is successful; next step is to find cycle start.

setup

Initialize ptr1 at head and ptr2 at meeting point

Two new pointers, ptr1 and ptr2, are set at head (node 3) and meeting point (node -4) respectively to find cycle start.

💡 Starting these pointers at different nodes allows locating the cycle entry by moving them at the same speed.

Line:

ptr1 = head
ptr2 = slow

💡 Two pointers start moving in tandem to find the cycle start node.

traverse

Move ptr1 and ptr2 one step forward

Both ptr1 and ptr2 move one step forward: ptr1 from node 3 to 2, ptr2 from node -4 to 2.

💡 Moving both pointers at the same speed guarantees they meet at the cycle start node.

Line:

ptr1 = ptr1.next
ptr2 = ptr2.next

💡 Pointers are converging on the cycle start node.

compare

Pointers meet at cycle start node

ptr1 and ptr2 meet at node with value 2, identifying the start of the cycle.

💡 Meeting at the same node confirms the cycle entry point in the linked list.

Line:

while ptr1 != ptr2:
    ptr1 = ptr1.next
    ptr2 = ptr2.next
return ptr1

💡 The cycle start node is found by moving pointers at equal speed from head and meeting point.

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

def detectCycle(head):
    slow = fast = head  # STEP 1
    while fast and fast.next:  # STEP 2-8 loop
        slow = slow.next  # STEP 2,4,6
        fast = fast.next.next  # STEP 3,5,7
        if slow == fast:  # STEP 8
            break
    else:
        return None
    ptr1 = head  # STEP 9
    ptr2 = slow  # STEP 9
    while ptr1 != ptr2:  # STEP 10-11 loop
        ptr1 = ptr1.next  # STEP 10
        ptr2 = ptr2.next  # STEP 10
    return ptr1  # STEP 11

# Example usage:
# node4 = ListNode(-4)
# node3 = ListNode(0, node4)
# node2 = ListNode(2, node3)
# node1 = ListNode(3, node2)
# node4.next = node2  # cycle
# print(detectCycle(node1).val)  # Output: 2 (cycle start)

📊

Linked List Cycle II - Start of Cycle - Watch the Algorithm Execute, Step by Step

Watching the pointers move step-by-step reveals how Floyd’s algorithm detects cycles and locates their start without extra memory.

advance

3

→

2

→

0

→

-4

advance

3

→

2

→

0

→

-4

advance

3

→

2

→

0

→

-4

advance

3

→

2

→

0

→

-4

advance

3

→

2

→

0

→

-4

advance

3

→

2

→

0

→

-4

compare

3

→

2

→

0

→

-4

compare

3

→

2

→

0

→

-4

advance

3

→

2

→

0

→

-4

compare

3

→

2

→

0

→

-4

compare

3

→

2

→

0

→

-4

Result: 1

Key Takeaways

✓ Floyd’s algorithm detects a cycle by moving two pointers at different speeds until they meet inside the cycle.

This meeting point inside the cycle is not obvious from code alone but is clear when watching pointers move.

✓ After detecting a cycle, resetting one pointer to head and moving both pointers at the same speed finds the cycle start.

The logic behind why moving both pointers at the same speed leads to the cycle start is easier to grasp visually.

✓ The cycle start node is the first node where the two pointers meet after the second phase of traversal.

Seeing the pointers converge on the exact node clarifies the algorithm’s correctness and final output.

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. Consider the following Python code implementing the optimized fast-slow pointer approach for detecting a cycle in a circular array. Given the input nums = [2, -1, 1, 2, 2], what is the return value of the function circularArrayLoop(nums)?

easy

A. Raises an IndexError

B. false

C. true

D. Infinite loop

Solution

1. Step 1: Trace first iteration with i=0

   Start at index 0, direction is positive. Moves: 0->2->3->0 forms a cycle of length >1 with consistent direction.

2. Step 2: Detect cycle and return true

   Fast and slow pointers meet at index 0, cycle length >1, so function returns true.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Cycle detected correctly for input [2, -1, 1, 2, 2] [OK]

Hint: Trace fast and slow pointers until they meet [OK]

Common Mistakes:

• Confusing direction checks
• Missing cycle length 1 check
• Miscomputing next index modulo

3. Given the following code for finding the middle node of a linked list, what is the value returned when the input list is 1 -> 2 -> 3 -> 4?

easy

A. 2

B. 3

C. 4

D. 1

Solution

1. Step 1: Trace slow and fast pointers

   Initial: slow=1, fast=1; Iteration 1: slow=2, fast=3; Iteration 2: fast.next is null, loop ends.

2. Step 2: Return slow's value

   Slow points to node with value 3 at loop end.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   For even length, returns second middle node (3) [OK]

Hint: Fast pointer moves twice as fast; slow ends at middle [OK]

Common Mistakes:

• Returning first middle node for even length
• Off-by-one errors in loop condition
• Confusing slow and fast pointer positions

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