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. You are given a problem where you repeatedly transform a number by replacing it with the sum of the squares of its digits. The goal is to determine if this process eventually reaches 1 or falls into a repeating cycle. Which algorithmic approach is best suited to efficiently detect cycles in this implicit sequence without extra space?

easy

A. Dynamic Programming with memoization to store intermediate results

B. Breadth-First Search (BFS) to explore all possible transformations

C. Greedy approach to pick the next number with the smallest digit sum

D. Floyd's Cycle Detection (Fast and Slow Pointers) to detect cycles in sequences

Solution

1. Step 1: Understand the problem as detecting cycles in a sequence generated by a function

   The problem involves repeatedly applying a function to a number to generate a sequence. Detecting if this sequence reaches 1 or cycles indefinitely is a classic cycle detection problem.

2. Step 2: Identify Floyd's Cycle Detection as the optimal approach

   Floyd's fast and slow pointers efficiently detect cycles in sequences without extra space, unlike DP or BFS which require additional memory or are not suited for implicit sequences.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Cycle detection in implicit sequences -> Floyd's algorithm [OK]

Hint: Cycle detection in sequences -> Floyd's fast-slow pointers [OK]

Common Mistakes:

• Confusing cycle detection with DP or BFS approaches

3. Consider the following code snippet for detecting and returning the length of a cycle in a linked list. Given the linked list: 3 -> 2 -> 0 -> -4 -> (back to node with value 2), what is the returned cycle length?

easy

A. 2

B. 3

C. 4

D. 0

Solution

1. Step 1: Trace fast and slow pointers until they meet

   Slow moves 1 step, fast moves 2 steps. They meet at node with value 2 after some iterations.

2. Step 2: Count cycle length by moving slow pointer until it meets fast again

   Starting from node 2, slow moves through nodes 0, -4, then back to 2, counting 3 nodes total.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Cycle length is nodes 2 -> 0 -> -4 -> back to 2 = 3 [OK]

Hint: Cycle length equals number of unique nodes in loop [OK]

Common Mistakes:

• Off-by-one counting cycle length
• Confusing meeting point with cycle start
• Returning 0 when cycle exists

4. Given the following code snippet for splitting a linked list into k parts, and the input list 1->2->3 with k=5, what is the value of parts[2] (the head node's value of the third part) in the returned array?

easy

A. null

B. 3

C. 2

D. 1

Solution

1. Step 1: Count total nodes and compute sizes

   List length = 3, k = 5, so part_size = 0, remainder = 3.

2. Step 2: Assign nodes to parts

   First 3 parts get 1 node each (due to remainder), last 2 parts get null (empty).

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   parts[0]=1, parts[1]=2, parts[2]=3, parts[3]=null, parts[4]=null, so parts[2] points to node with value 3 [OK]

Hint: Parts beyond list length are null [OK]

Common Mistakes:

• Assuming all parts have nodes
• Off-by-one in indexing parts
• Confusing node values with indices

5. Consider the following buggy code snippet for splitting a linked list into k parts. Which line contains the subtle bug that can cause parts to remain connected, leading to incorrect output or infinite loops?

medium

A. Line where current.next is set to null (missing in this code)

B. Line where parts[i] is assigned

C. Line where remainder is decremented

D. Line where total_nodes is counted

Solution

1. Step 1: Identify missing link break

   The code comments out the lines that break the link after each part, so parts remain connected.

2. Step 2: Understand impact

   Without setting current.next = null, parts share nodes, causing incorrect output or infinite loops.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Breaking links is essential to separate parts [OK]

Hint: Always break links to separate parts [OK]

Common Mistakes:

• Forgetting to break links
• Misplacing remainder decrement
• Incorrectly assigning parts[i]