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. Consider the following Python code implementing Floyd's cycle detection and cycle start finding algorithm. Given the linked list: 1 -> 2 -> 3 -> 4 -> 2 (cycle starts at node with value 2), what value does the function return?

easy

A. 4

B. 3

C. 2

D. None

Solution

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

   Slow moves 1 step, fast moves 2 steps. They meet inside the cycle at node with value 3 or 4 after some iterations.

2. Step 2: Reset one pointer to head and move both one step at a time

   Both pointers meet at node with value 2, which is the cycle start.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Cycle start node value is 2 as per algorithm [OK]

Hint: Cycle start found by meeting pointers after reset [OK]

Common Mistakes:

• Returning meeting point instead of cycle start
• Off-by-one error in pointer movement
• Returning None incorrectly

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

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. Consider this buggy code snippet for finding the nth node from the end using two pointers. Which line contains the bug?

medium

A. Line 9: return statement returning slow pointer

B. Line 7: while loop condition

C. Line 3: for loop advancing fast pointer

D. Line 2: initializing slow pointer

Solution

1. Step 1: Analyze return statement

   The function returns the slow pointer node instead of its value, which is inconsistent with expected output.

2. Step 2: Confirm other lines are correct

   Fast pointer advances n-1 steps, loop condition is correct, and slow pointer initialization is standard.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Returning node instead of value causes confusion or errors [OK]

Hint: Return node.val, not node reference [OK]

Common Mistakes:

• Not checking if n > length
• Advancing fast pointer fewer steps
• Returning node instead of value

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]