Middle of the Linked List

▶

Steps

setup

Initialize slow and fast pointers at head

Both slow and fast pointers are set to the head of the list, which is the node with value 1.

💡 Starting both pointers at the head ensures they traverse the list together from the beginning.

Line:

slow = head
fast = head

💡 Both pointers start at the same node, ready to begin traversal.

compare

Check loop condition: fast and fast.next exist

The algorithm checks if fast and fast.next are not null to continue the loop.

💡 This condition ensures the fast pointer can safely move two steps ahead without reaching beyond the list.

Line:

while fast and fast.next:

💡 The loop will execute because the fast pointer can move forward.

traverse

Move slow pointer one step forward

The slow pointer moves from node 1 to node 2, advancing one node.

💡 Slow pointer moves one step to track the middle position gradually.

Line:

slow = slow.next

💡 Slow pointer now points to the second node, moving steadily through the list.

traverse

Move fast pointer two steps forward

The fast pointer moves from node 1 to node 3, skipping one node.

💡 Fast pointer moves twice as fast to reach the end quicker.

Line:

fast = fast.next.next

💡 Fast pointer now points to the third node, moving two nodes per iteration.

compare

Check loop condition: fast and fast.next exist

Check if fast (node 3) and fast.next (node 4) are not null to continue looping.

💡 Ensures fast pointer can move two steps again safely.

Line:

while fast and fast.next:

💡 Loop continues as fast pointer can still advance.

traverse

Move slow pointer one step forward

Slow pointer moves from node 2 to node 3.

💡 Slow pointer continues moving one node at a time.

Line:

slow = slow.next

💡 Slow pointer now points to the middle candidate node.

traverse

Move fast pointer two steps forward

Fast pointer moves from node 3 to node 5, skipping node 4.

💡 Fast pointer moves two nodes ahead to approach the list end.

Line:

fast = fast.next.next

💡 Fast pointer now points to the last node in the list.

compare

Check loop condition: fast and fast.next exist

Check if fast (node 5) and fast.next (null) exist to continue looping.

💡 Loop condition fails because fast.next is null, meaning fast is at the end.

Line:

while fast and fast.next:

💡 Traversal ends as fast pointer reached the list end.

reconstruct

Return slow pointer as middle node

The slow pointer currently points to the middle node with value 3, which is returned as the result.

💡 Returning slow pointer gives the middle node without counting nodes explicitly.

Line:

return slow

💡 Slow pointer correctly identifies the middle node after traversal.

reconstruct

Final state: middle node value is 3

The algorithm ends with the middle node identified as the node with value 3.

💡 This confirms the middle node for the input list is the third node.

💡 The middle node is the exact center of the list with odd length.

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

def middleNode(head: ListNode) -> ListNode:
    slow = head  # STEP 1
    fast = head  # STEP 1
    while fast and fast.next:  # STEP 2,5,8
        slow = slow.next  # STEP 3,6
        fast = fast.next.next  # STEP 4,7
    return slow  # STEP 9

# Example usage:
# head = ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5)))))
# print(middleNode(head).val)  # Output: 3

📊

Middle of the Linked List - Watch the Algorithm Execute, Step by Step

Watching the pointers move side-by-side reveals how the fast pointer skipping nodes helps the slow pointer land exactly at the middle without counting nodes explicitly.

setup

1

→

2

→

3

→

4

→

5

compare

1

→

2

→

3

→

4

→

5

advance

1

→

2

→

3

→

4

→

5

advance

1

→

2

→

3

→

4

→

5

compare

1

→

2

→

3

→

4

→

5

advance

1

→

2

→

3

→

4

→

5

advance

1

→

2

→

3

→

4

→

5

compare

1

→

2

→

3

→

4

→

5

return

1

→

2

→

3

→

4

→

5

Result: 3

done

1

→

2

→

3

→

4

→

5

Result: 3

Key Takeaways

✓ The fast pointer moves twice as fast as the slow pointer, allowing the slow pointer to land exactly at the middle node when the fast pointer reaches the end.

This insight is difficult to grasp from code alone because the relationship between pointer speeds and the middle position is implicit.

✓ The loop condition ensures the fast pointer never moves beyond the list bounds, preventing errors and signaling when the middle is found.

Seeing the condition visually clarifies why the loop stops exactly at the right time.

✓ Returning the slow pointer after traversal gives the middle node without needing to count nodes or know the list length beforehand.

This shows the power of two-pointer technique to solve problems efficiently in one pass.

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. Examine the following buggy code for cycle detection using fast and slow pointers. Which line contains the subtle bug that can cause incorrect cycle detection or runtime error?

medium

A. Line 3: while fast and fast.next:

B. Line 5: slow = slow.next

C. Line 6: fast = fast.next.next

D. Line 4: if slow == fast:

Solution

1. Step 1: Understand pointer initialization and loop

   Both slow and fast start at head. The loop checks fast and fast.next to avoid null dereference.

2. Step 2: Identify when pointers are compared

   Comparing slow == fast before moving pointers causes immediate true at start (both at head), falsely detecting a cycle. Moving pointers first then comparing avoids this.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Comparison must happen after moving pointers to avoid false positive [OK]

Hint: Check pointers after moving, not before, to avoid false positives [OK]

Common Mistakes:

• Comparing pointers before moving them
• Not checking fast.next before advancing fast

3. Examine the following code snippet intended to detect the start of a cycle in a linked list. Identify the line containing the subtle bug that can cause a runtime error or infinite loop.

medium

A. Line 5: fast = fast.next.next

B. Line 3: while fast:

C. Line 7: if slow == fast:

D. Line 11: while ptr1 != ptr2:

Solution

1. Step 1: Check loop condition safety

   The loop condition only checks if fast is not None, but fast.next may be None, so fast.next.next can cause an exception.

2. Step 2: Identify fix

   The loop condition should check both fast and fast.next to avoid null pointer exceptions.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Accessing fast.next.next without checking fast.next causes runtime error [OK]

Hint: Always check fast and fast.next before accessing fast.next.next [OK]

Common Mistakes:

• Missing fast.next check
• Returning meeting point as cycle start
• Infinite loop due to wrong loop condition

4. What is the space complexity of the recursive reorderList implementation shown below, considering a linked list of length n?

medium

A. O(log n) -- recursion divides list in halves

B. O(1) -- only constant extra pointers used

C. O(n) -- recursion stack grows linearly with list length

D. O(n^2) -- nested recursive calls cause quadratic space

Solution

1. Step 1: Analyze recursion depth

   Each recursive call moves one node forward, so recursion depth is n.

2. Step 2: Determine space usage

   Each call adds a stack frame, so total auxiliary space is O(n).

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Recursion stack grows linearly with input size [OK]

Hint: Recursion depth equals list length -> O(n) space [OK]

Common Mistakes:

• Assuming recursion is O(1) space
• Confusing recursion with divide-and-conquer
• Thinking nested calls multiply space

5. Suppose the Happy Number problem is extended to allow negative integers as input. Which modification to the optimal algorithm is necessary to correctly handle negative inputs?

hard

A. Add absolute value conversion before processing digits to handle negatives

B. Add negative numbers to the cycle set to detect cycles

C. Modify get_next to handle negative digits separately

D. No change needed; negative numbers will eventually reach 1 or cycle

Solution

1. Step 1: Understand digit extraction for negative numbers

   Digit extraction using modulo and division assumes non-negative numbers. Negative inputs cause incorrect digit processing.

2. Step 2: Convert input to absolute value before processing

   Taking absolute value ensures digits are correctly extracted and sum of squares computed properly.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Absolute value fixes digit extraction for negatives [OK]

Hint: Digit extraction requires non-negative numbers [OK]

Common Mistakes:

• Assuming negative inputs work without modification