Linked List Cycle Length

▶

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 before traversal begins.

💡 Starting both pointers at head ensures they traverse the list from the same starting point, enabling cycle detection.

Line:

slow = fast = head

💡 Both pointers begin together, ready to move at different speeds to detect a cycle.

traverse

Move slow by one step, fast by two steps

Slow pointer moves from node 3 to node 2. Fast pointer moves from node 3 to node 0 by skipping node 2.

💡 Moving pointers at different speeds helps detect cycles when they meet inside the loop.

Line:

slow = slow.next
fast = fast.next.next

💡 Fast pointer moves faster and may catch up to slow pointer if a cycle exists.

traverse

Move slow by one step, fast by two steps again

Slow moves from node 2 to node 0. Fast moves from node 0 to node 2 by skipping node -4, completing one cycle lap.

💡 Fast pointer moves two steps, potentially catching slow inside the cycle.

Line:

slow = slow.next
fast = fast.next.next

💡 Fast pointer is now inside the cycle and approaching slow pointer.

traverse

Move slow by one step, fast by two steps again

Slow moves from node 0 to node -4. Fast moves from node 2 to node -4 by skipping node 0.

💡 Pointers continue moving; fast pointer is closing in on slow pointer.

Line:

slow = slow.next
fast = fast.next.next

💡 Both pointers now point to the same node, indicating cycle detection.

insert

Cycle detected: initialize length counter

Since slow equals fast, a cycle is detected. Initialize length counter to 1 and prepare to count cycle length.

💡 Detecting the cycle meeting point is crucial to start measuring the cycle length.

Line:

if slow == fast:
    length = 1

💡 The meeting point confirms a cycle exists; now we measure its length.

traverse

Move slow one step to start cycle length count

Move slow pointer one step forward from node -4 to node 2 to begin counting cycle length.

💡 Moving slow pointer prepares to traverse the cycle once to count its length.

Line:

slow = slow.next

💡 Starting the cycle length count by moving slow forward inside the cycle.

traverse

Increment length counter and move slow one step

Since slow (2) is not equal to fast (4), increment length to 2 and move slow to node 0.

💡 Counting nodes in the cycle by moving slow until it meets fast again.

Line:

while slow != fast:
    length += 1
    slow = slow.next

💡 Cycle length counting continues as slow moves through the cycle nodes.

traverse

Increment length counter and move slow one step again

Slow pointer moves from node 0 to node -4, incrementing length to 3. Slow still not equal to fast.

💡 Continuing to traverse the cycle to count all nodes in it.

Line:

length += 1
slow = slow.next

💡 Counting all nodes in the cycle by moving slow pointer.

compare

Slow meets fast again, cycle length counting complete

Slow pointer equals fast pointer again at node -4, ending the cycle length count.

💡 Meeting again means one full cycle traversal is done, confirming the cycle length.

Line:

while slow != fast:
    ...
return length

💡 Cycle length is the number of nodes traversed in the cycle.

reconstruct

Return the cycle length

The function returns the cycle length 3 as the final answer.

💡 Returning the computed cycle length completes the algorithm.

Line:

return length

💡 The cycle length is the number of nodes in the detected cycle.

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

def cycle_length(head):
    if not head:
        return 0  # STEP 1
    slow = fast = head  # STEP 1
    while fast and fast.next:  # STEP 2
        slow = slow.next  # STEP 2
        fast = fast.next.next  # STEP 2
        if slow == fast:  # STEP 5
            length = 1  # STEP 5
            slow = slow.next  # STEP 6
            while slow != fast:  # STEP 7-9
                length += 1  # STEP 7-8
                slow = slow.next  # STEP 7-8
            return length  # STEP 10
    return 0  # STEP 3

# Example usage:
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
    print(cycle_length(node1))  # Output: 3

📊

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

Watching the pointers move step-by-step reveals how the fast pointer laps the slow pointer inside the cycle, and how the cycle length is counted by a second traversal.

setup

3

→

2

→

0

→

-4

advance

3

→

2

→

0

→

-4

advance

3

→

2

→

0

→

-4

compare

3

→

2

→

0

→

-4

insert

3

→

2

→

0

→

-4

advance

3

→

2

→

0

→

-4

Result: 1

advance

3

→

2

→

0

→

-4

Result: 2

advance

3

→

2

→

0

→

-4

Result: 3

compare

3

→

2

→

0

→

-4

Result: 3

reconstruct

3

→

2

→

0

→

-4

Result: 3

Key Takeaways

✓ The fast pointer moves twice as fast as the slow pointer and will eventually meet slow inside the cycle if one exists.

This insight is hard to see from code alone because the meeting point depends on relative speeds and cycle structure.

✓ Once the cycle is detected, counting the cycle length requires traversing the cycle once starting from the meeting point.

Understanding that the cycle length is the number of nodes in one full loop is easier when visualized step-by-step.

✓ If fast or fast.next becomes null, it means no cycle exists and the function returns 0 immediately.

This early exit condition is critical but subtle in code; visualization shows why traversal stops.

Practice

1. You are given a singly linked list and an integer n. The task is to remove the n-th node from the end of the list in a single pass without using extra space for storing nodes. Which approach guarantees this optimal solution?

easy

A. Traverse the list twice: first to count nodes, second to remove the target node.

B. Sort the list first, then remove the node at position length - n.

C. Use two pointers with a fixed gap of n+1 nodes, moving together until the fast pointer reaches the end.

D. Use a dynamic programming approach to store intermediate results for each node.

Solution

1. Step 1: Understand the problem constraints

   The problem requires removing the n-th node from the end in one pass without extra storage.

2. Step 2: Identify the two-pointer technique for single-pass removal

   Using two pointers with a gap of n+1 nodes ensures the slow pointer stops just before the target node, allowing removal in one pass.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Two-pointer approach is classic for single-pass linked list problems [OK]

Hint: Two pointers with gap n+1 enable single-pass removal [OK]

Common Mistakes:

• Using two passes instead of one
• Trying to sort the list which is unnecessary
• Confusing DP with linked list traversal

2. You are given a singly linked list and asked to reorder it so that the nodes are arranged in the order: first node, last node, second node, second last node, and so on. Which approach guarantees an optimal in-place solution with O(n) time and O(1) extra space?

easy

A. Use a brute force approach by storing all nodes in an array and then rearranging pointers.

B. Use dynamic programming to store intermediate reorder states and build the final list.

C. Recursively reorder the list by traversing to the end and merging nodes from both ends.

D. Find the middle of the list using fast and slow pointers, reverse the second half, then merge the two halves.

Solution

1. Step 1: Identify the problem constraints

   The problem requires reordering the list in-place with O(n) time and O(1) space.

2. Step 2: Evaluate approaches

   Brute force uses extra space, recursion uses O(n) stack space, and DP is not applicable here. The fast-slow pointer approach finds the middle, reverses the second half, and merges in-place efficiently.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Fast-slow pointer approach is classic for in-place reorder [OK]

Hint: Fast-slow pointer + reverse + merge is classic in-place reorder [OK]

Common Mistakes:

• Thinking recursion is O(1) space
• Using DP for linked list reorder
• Assuming array storage is in-place

3. Identify the bug in the following code snippet for finding the duplicate number using Floyd's cycle detection:

medium

A. The initialization of slow and fast pointers is incorrect

B. The second while loop incorrectly updates fast pointer

C. The first while loop condition causes an infinite loop

D. The return statement should return fast instead of slow

Solution

1. Step 1: Examine the first while loop condition

   The loop condition is while slow != fast, but slow and fast are initialized to the same value, so the loop never runs, causing no intersection point found.

2. Step 2: Understand consequences

   Without the loop running, slow and fast pointers do not move, so the algorithm fails to detect the cycle and returns incorrect result or loops infinitely if code is modified.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Loop condition must allow first iteration; using while True with break is correct [OK]

Hint: First loop must run at least once to find intersection [OK]

Common Mistakes:

• Using while slow != fast before pointers move
• Incorrect pointer updates inside loops
• Returning wrong pointer at the end

4. The following code attempts to remove the nth node from the end of a singly linked list. Identify the line containing the subtle bug that causes incorrect behavior when removing the head node.

medium

A. Line 12: recurse(head)

B. Line 9: node.next = node.next.next

C. Line 3: def recurse(node):

D. Line 13: return head

Solution

1. Step 1: Understand dummy node role

   Dummy node is needed to handle removal of the head node safely.

2. Step 2: Identify missing dummy usage

   Calling recurse on head directly skips dummy, so removing head node breaks list or returns wrong head.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Missing dummy node causes incorrect removal of head [OK]

Hint: Always use dummy node to handle head removal edge case [OK]

Common Mistakes:

• Not using dummy node causing null pointer or wrong head
• Incorrectly unlinking nodes causing list corruption
• Off-by-one errors in recursion index

5. If the linked list nodes can be reused multiple times (i.e., the list is cyclic or can be traversed repeatedly), which modification is necessary to the optimal palindrome check algorithm?

hard

A. No modification needed; the current algorithm works as is.

B. Use a stack to store first half values instead of reversing to avoid modifying the list.

C. Convert the list to an array to handle multiple traversals safely.

D. Restore the reversed second half to original order after comparison to preserve list structure.

Solution

1. Step 1: Understand reuse implications

   If nodes are reused or list is cyclic, modifying it breaks future traversals.

2. Step 2: Restore list after palindrome check

   Reversing second half in-place must be undone to preserve original list structure.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Restoring reversed half ensures list integrity for reuse [OK]

Hint: Always restore list after in-place reversal if list is reused [OK]

Common Mistakes:

• Ignoring list restoration causing side effects
• Switching to stack approach unnecessarily increasing space
• Assuming array conversion is always better