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 need to determine if it reads the same forwards and backwards. Which approach guarantees an optimal solution with O(n) time and O(1) space complexity?

easy

A. Use fast and slow pointers to find the middle, reverse the second half in-place, then compare both halves.

B. Convert the linked list to an array and check palindrome by comparing elements from both ends.

C. Use a hash set to store visited nodes and check for palindrome by comparing values.

D. Use a recursive approach to compare nodes from start and end simultaneously.

Solution

1. Step 1: Identify the problem constraints

   The problem requires checking palindrome in O(n) time and O(1) space.

2. Step 2: Evaluate approaches

   Converting to array uses O(n) space, recursion uses O(n) stack space, and hash set is not suitable for palindrome check. Using fast and slow pointers to reverse second half in-place meets both time and space requirements.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Optimal approach uses fast-slow pointers and in-place reversal [OK]

Hint: Optimal palindrome check uses fast-slow pointers and in-place reversal [OK]

Common Mistakes:

• Assuming array conversion is optimal due to simplicity
• Believing recursion uses constant space
• Using hash sets for palindrome detection

2. Given the following code for checking if a linked list is a palindrome, what is the final return value when the input list is 1 -> 2 -> 1?

easy

A. Infinite loop

B. False

C. True

D. Raises an exception due to null pointer

Solution

1. Step 1: Trace fast and slow pointers

   For list 1 -> 2 -> 1, slow ends at node with value 2, fast reaches end.

2. Step 2: Reverse second half and compare

   Second half starting at 2 -> 1 is reversed to 1 -> 2. Compare nodes: 1==1, 2==2, all match, so return True.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Palindrome list returns True after correct reversal and comparison [OK]

Hint: Check pointer movement and reversed half comparison carefully [OK]

Common Mistakes:

• Misplacing slow pointer causing wrong half reversal
• Off-by-one error in comparison loop
• Forgetting to advance second_half_start pointer

3. What is the space complexity of the optimal palindrome linked list check that reverses the second half in-place?

medium

A. O(n) due to storing node values in an array

B. O(1) because reversal is done in-place without extra data structures

C. O(log n) due to recursion stack in reversal

D. O(n) due to recursion stack in reversal

Solution

1. Step 1: Identify auxiliary space usage

   The algorithm reverses the second half in-place using pointers, no extra arrays or stacks.

2. Step 2: Check for recursion stack

   The reversal is iterative, so no recursion stack space is used.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   In-place iterative reversal uses constant extra space [OK]

Hint: Iterative reversal uses O(1) space, recursion would add stack space [OK]

Common Mistakes:

• Confusing iterative reversal with recursive reversal
• Assuming array storage is needed for palindrome check
• Forgetting recursion stack space in complexity

4. Consider the following code snippet for palindrome check. Which line contains a subtle bug that can cause incorrect results on odd-length lists?

medium

A. Line where second_half_start is assigned by reversing slow

B. Line where slow pointer is advanced in the while loop

C. Line where first_half_start and second_half_start values are compared

D. Line where fast pointer is advanced in the while loop

Solution

1. Step 1: Understand midpoint selection

   For odd-length lists, slow points to the middle node, which should be skipped before reversal.

2. Step 2: Identify bug in reversal start

   Reversing from slow includes the middle node, causing mismatch in comparison.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Correct approach skips middle node before reversal on odd-length lists [OK]

Hint: Check if middle node is excluded before reversing second half [OK]

Common Mistakes:

• Reversing from slow without skipping middle node
• Incorrect fast/slow pointer advancement
• Not handling odd-length lists separately

5. If the linked list allows cycles (i.e., it may not terminate), which modification is necessary to safely find the nth node from the end?

hard

A. Use the two-pointer approach without changes; it will still work.

B. Use a stack to store nodes indefinitely until nth node is found.

C. First detect cycle using Floyd's cycle detection, then handle accordingly before finding nth node.

D. Increase n to a very large number to ensure traversal covers the cycle.

Solution

1. Step 1: Understand cycle impact

   If the list has a cycle, naive traversal will loop infinitely, breaking the algorithm.

2. Step 2: Detect and handle cycle

   Use Floyd's cycle detection to identify cycle presence and length, then adjust logic to avoid infinite loops.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Cycle detection is prerequisite for safe traversal [OK]

Hint: Detect cycle first to avoid infinite loops [OK]

Common Mistakes:

• Assuming list always terminates
• Using stack without cycle check
• Increasing n arbitrarily