1. Understanding the Problem

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

If there are two middle nodes (which happens when the list has an even number of elements), you must return the second middle node. For example, in a list of 1 -> 2 -> 3 -> 4 -> 5 -> 6, the middle nodes are 3 and 4. You should return the node with value 4.

The Core Constraint (The Trap):

Unlike an Array, a Singly Linked List does not have a length property, nor does it have indexes. You cannot simply query list[length / 2]. You only know where the head is, and you must follow the next pointers one by one to discover where the list actually ends.

2. The Naive Approach: The Two-Pass Traversal

The most intuitive way to solve this is to treat it like a geometry problem: first, measure the total distance, then walk exactly half that distance.

Pass 1: You start at the head and traverse the entire list until you hit null, keeping a count of every node you see to determine the total length (N).

Pass 2: You start back at the head again and traverse exactly N / 2 steps forward. The node you land on is the middle node.

Trade-off Analysis

While this logic works perfectly and is completely valid, it is slightly inefficient:

• Time Complexity: O(N) — You traverse the list 1.5 times. While this simplifies to O(N) in Big-O notation, iterating over a massive dataset twice when it could be done once is heavily scrutinized in senior-level interviews.
• Space Complexity: O(1) — We only use integer counters, so space is constant.

3. The Optimal Approach: Fast and Slow Pointers (One Pass)

To pass a senior-level technical interview, we want to find the middle in exactly one single pass. We can achieve this by employing the Tortoise and Hare approach we used in the Linked List Cycle problem.

Imagine two friends going for a run on a trail. The Fast runner runs exactly twice as fast as the Slow runner. If they both start at the beginning of the trail at the exact same time, where will the Slow runner be when the Fast runner crosses the finish line?

Mathematically, because the Slow runner is moving at half the speed, they will be standing at the exact middle of the trail when the Fast runner finishes. We can apply this exact logic to our pointers to find the middle node instantly!

4. The Logic Step-by-Step

1. Initialize Pointers: Set a slow pointer and a fast pointer, both starting at the head of the linked list.
2. The Race: Create a loop that continues as long as fast is not null AND fast.next is not null. (We must check fast.next because the fast pointer takes two steps at a time, and attempting to jump off a null node will throw a NullPointerException).
   • Move the slow pointer forward by 1 step: slow = slow.next.
   • Move the fast pointer forward by 2 steps: fast = fast.next.next.
3. The Finish Line: The loop automatically breaks when fast reaches the end of the list. Due to the even/odd logic of the `while` condition, when the loop ends, slow is guaranteed to be resting on the exact middle node (or the second middle node in an even-length list).
4. Return the slow node.

5. Complexity Analysis

• Time Complexity: O(N) — We traverse the linked list just once. The fast pointer reaches the end in exactly N/2 operations, making this highly optimal.
• Space Complexity: O(1) — We only use two temporary pointers (slow and fast). We have successfully achieved constant space with zero extra data structures!

6. Code Implementations

Expand the sections below to see the optimal O(1) space "Fast and Slow Pointer" implementations across different languages.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution:
    def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
        slow = head
        fast = head
        
        # Fast moves 2 steps, Slow moves 1 step
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            
        # When fast reaches the end, slow is at the middle
        return slow

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode middleNode(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        
        // Fast moves 2 steps, Slow moves 1 step
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        
        // When fast reaches the end, slow is at the middle
        return slow;
    }
}

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        ListNode* slow = head;
        ListNode* fast = head;
        
        // Fast moves 2 steps, Slow moves 1 step
        while (fast != nullptr && fast->next != nullptr) {
            slow = slow->next;
            fast = fast->next->next;
        }
        
        // When fast reaches the end, slow is at the middle
        return slow;
    }
};

7. Conclusion: You Are Ready

Congratulations, you have just mastered one of the most elegant and frequently tested patterns in computer science! The Fast and Slow Pointers technique is a brilliant demonstration of how manipulating iteration speeds can yield powerful topological insights about a dataset. Keep this mental model of the "runners on a trail" active. You will use this exact mid-point finding logic as a crucial helper function for solving highly advanced problems like Palindrome Linked List and Sort List!