Problem Description

You are given the head of a singly linked list. Your task is to find and return the middle node of this linked list.

The middle node is defined as follows:

• If the linked list has an odd number of nodes, return the node at the exact center position
• If the linked list has an even number of nodes, there will be two middle nodes - return the second middle node

For example:

• If the linked list is 1 -> 2 -> 3 -> 4 -> 5, the middle node is 3 (the third node)
• If the linked list is 1 -> 2 -> 3 -> 4 -> 5 -> 6, there are two middle nodes (3 and 4), so you should return 4 (the second middle node)

The solution uses the two-pointer technique (also known as the tortoise and hare algorithm):

• Initialize two pointers, slow and fast, both starting at the head
• Move slow one step at a time (slow = slow.next)
• Move fast two steps at a time (fast = fast.next.next)
• Continue this process while fast and fast.next are not None
• When fast reaches the end, slow will be at the middle node

This works because fast moves twice as fast as slow. When fast reaches the end of the list, slow will have traveled exactly half the distance, positioning it at the middle node. For even-length lists, this naturally gives us the second middle node as required.

Intuition

The key insight comes from thinking about the relationship between distance and speed. Imagine two runners on a track - one runs twice as fast as the other. When the faster runner completes the full track, where would the slower runner be? Exactly at the halfway point!

This same principle applies to traversing a linked list. If we have two pointers moving through the list at different speeds - one moving one node at a time and another moving two nodes at a time - when the faster pointer reaches the end, the slower pointer will be at the middle.

Why does this work mathematically? Let's say the linked list has n nodes:

• The slow pointer moves 1 step per iteration
• The fast pointer moves 2 steps per iteration
• When fast has traversed n nodes (reaching the end), it took n/2 iterations
• In those same n/2 iterations, slow moved n/2 nodes, placing it exactly at the middle

For odd-length lists (like 5 nodes), slow ends up at position ⌊5/2⌋ + 1 = 3 (the exact middle). For even-length lists (like 6 nodes), slow ends up at position 6/2 = 3, but since we count from position 0, this gives us the 4th node, which is the second middle node - exactly what we want!

The beauty of this approach is that we don't need to know the length of the list beforehand. We don't need to traverse it once to count nodes and then traverse again to find the middle. Everything happens in a single pass, making this an elegant O(n) time solution with O(1) space complexity.

Learn more about Linked List and Two Pointers patterns.

Solution Approach

The implementation uses the fast and slow pointer technique (Floyd's Tortoise and Hare algorithm) to find the middle node in a single pass.

Algorithm Steps:

1. Initialize two pointers: Both slow and fast start at the head of the linked list

   slow = fast = head

2. Traverse the linked list with different speeds:

   • The loop continues while both fast and fast.next exist
   • This condition ensures we don't get a null pointer error when fast tries to jump two nodes

   while fast and fast.next:

3. Move the pointers:

   • slow moves one step forward: slow = slow.next
   • fast moves two steps forward: fast = fast.next.next
   • Python allows simultaneous assignment, so we can write:

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

4. Return the middle node: When the loop exits, slow points to the middle node

   return slow

Why the loop condition works:

• fast checks if the fast pointer itself exists (prevents error when list has odd length)
• fast.next checks if fast can make another two-step jump (prevents error when list has even length)
• When either becomes None, we've reached or passed the end of the list

Example walkthrough:

• For list 1->2->3->4->5:

  • Initially: slow at 1, fast at 1
  • Iteration 1: slow at 2, fast at 3
  • Iteration 2: slow at 3, fast at 5
  • Loop ends (fast.next is None), return node 3

• For list 1->2->3->4:

  • Initially: slow at 1, fast at 1
  • Iteration 1: slow at 2, fast at 3
  • Iteration 2: slow at 3, fast is None
  • Loop ends, return node 3 (the second middle node)

Time Complexity: O(n) where n is the number of nodes - we traverse at most n/2 iterations Space Complexity: O(1) - only using two pointers regardless of input size

Example Walkthrough

Let's walk through finding the middle node of the linked list: 1 -> 2 -> 3 -> 4 -> 5

Initial Setup:

• Both slow and fast pointers start at the head (node 1)
• List visualization: [1] -> 2 -> 3 -> 4 -> 5
  • slow points to node 1
  • fast points to node 1

Iteration 1:

• Check condition: fast (node 1) exists ✓ and fast.next (node 2) exists ✓
• Move pointers:
  • slow moves one step: slow = slow.next → now at node 2
  • fast moves two steps: fast = fast.next.next → now at node 3
• List visualization: 1 -> [2] -> (3) -> 4 -> 5
  • [2] = slow pointer position
  • (3) = fast pointer position

Iteration 2:

• Check condition: fast (node 3) exists ✓ and fast.next (node 4) exists ✓
• Move pointers:
  • slow moves one step: now at node 3
  • fast moves two steps: now at node 5
• List visualization: 1 -> 2 -> [3] -> 4 -> (5)
  • [3] = slow pointer position
  • (5) = fast pointer position

Iteration 3:

• Check condition: fast (node 5) exists ✓ but fast.next is None ✗
• Loop terminates
• Return slow which points to node 3

Result: Node 3 is correctly identified as the middle node of the 5-node list.

For an even-length list like 1 -> 2 -> 3 -> 4, the algorithm would proceed:

• Start: slow and fast at node 1
• After iteration 1: slow at node 2, fast at node 3
• After iteration 2: slow at node 3, fast becomes None (moved past node 4)
• Returns node 3, which is the second middle node (nodes 2 and 3 are both "middle", we return the second one)

Solution Implementation

Time and Space Complexity

Time Complexity: O(n) where n is the number of nodes in the linked list. The algorithm uses two pointers - a slow pointer that moves one step at a time and a fast pointer that moves two steps at a time. The fast pointer will reach the end of the list after traversing approximately n/2 iterations (since it moves twice as fast), at which point the loop terminates. Therefore, the slow pointer visits approximately n/2 nodes and the fast pointer visits approximately n nodes, resulting in a total time complexity of O(n).

Space Complexity: O(1) - The algorithm only uses two pointer variables (slow and fast) regardless of the size of the input linked list. No additional data structures or recursive calls are made that would scale with the input size, making the space complexity constant.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Loop Condition

A common mistake is using only while fast.next: or while fast: as the loop condition instead of while fast and fast.next:.

Why it's wrong:

• Using only while fast.next: will cause a NullPointerException/AttributeError when fast itself becomes None (happens with odd-length lists)
• Using only while fast: will cause an error when trying to access fast.next.next if fast.next is None (happens with even-length lists)

Incorrect implementation:

# This will fail for odd-length lists
while fast.next:  # Error when fast is None
    slow = slow.next
    fast = fast.next.next

Correct implementation:

# Check both fast and fast.next
while fast and fast.next:
    slow = slow.next
    fast = fast.next.next

2. Moving Pointers in Wrong Order

Another pitfall is updating the pointers in the wrong sequence when not using simultaneous assignment.

Why it's wrong: If you update fast first using sequential assignments, you lose the reference needed for updating slow.

Incorrect implementation:

while fast and fast.next:
    fast = fast.next.next  # Wrong: updating fast first
    slow = slow.next       # This still works but can lead to confusion

Better implementations:

# Option 1: Update slow first
while fast and fast.next:
    slow = slow.next
    fast = fast.next.next

# Option 2: Use simultaneous assignment (Python feature)
while fast and fast.next:
    slow, fast = slow.next, fast.next.next

3. Off-by-One Error for Even-Length Lists

Some might mistakenly think they need special handling for even-length lists to return the second middle node.

Why it's wrong: The algorithm naturally returns the second middle node for even-length lists. Adding extra logic is unnecessary and can introduce bugs.

Incorrect approach:

# Unnecessary complexity
def middleNode(self, head):
    # Count nodes first
    count = 0
    current = head
    while current:
        count += 1
        current = current.next
  
    # Find middle based on count
    middle_index = count // 2
    current = head
    for _ in range(middle_index):
        current = current.next
    return current

Correct approach: The two-pointer technique automatically handles both odd and even cases without special logic.

4. Not Handling Edge Cases

While the algorithm handles most cases well, ensure you consider:

• Single node list (works correctly as-is)
• Two node list (returns the second node correctly)

The beauty of the while fast and fast.next: condition is that it handles all these edge cases without additional checks.