Middle of the Linked List — Fast and Slow Pointer You Must Know Cold

Problem Statement#

Given the head of a singly linked list, return the middle node. If there are two middle nodes, return the second middle node.

Constraints:

• The number of nodes in the list is in the range [1, 100]
• 1 <= Node.val <= 100
• Single-pass solution expected
• Target time complexity: O(n); target extra space: O(1)

Input:  head = [1, 2, 3, 4, 5, 6]
Output: Node with value 4 (the second middle node)

Why This Problem Matters#

Finding the middle of a linked list in a single pass with O(1) space is the gateway to half the linked-list problems in interview loops. Palindrome Linked List (LC 234), Reorder List (LC 143), Sort List (LC 148), and Delete the Middle Node (LC 2095) all need to find the middle as their first step. If you find the middle by counting length first and then walking again, you are taking two passes and writing more code than necessary. The fast/slow pointer collapses both passes into one elegant loop.

Beyond the specific problem, this technique teaches you the core mental model of relative-speed pointers: if fast moves at twice the rate of slow, when fast reaches the end, slow is at the halfway point. This ratio-based reasoning extends to finding the node k steps from the end (the n-gap technique for LC 19), detecting cycles (Floyd's algorithm for LC 141), and locating the cycle entry point (LC 142). Mastering the loop conditions of the fast/slow primitive pays off across the entire track.

Interviewers also love the variation: "what if you want the first middle for an even-length list?" The answer requires a one-line change in the loop condition, and being able to answer it instantly signals fluency rather than memorization. This problem rewards candidates who understand the mechanics, not just the code.

The Core Insight#

The fast pointer moves two nodes per step; the slow pointer moves one. After t steps, slow is at position t and fast is at position 2t. When fast reaches or passes the last node, slow is at the middle. Whether slow lands on the first or second middle for even-length lists depends entirely on the loop condition: while fast and fast.next lands on the second middle, while while fast.next and fast.next.next lands on the first.

Visual Dry Run#

Odd-length list [1, 2, 3, 4, 5]:

Even-length list [1, 2, 3, 4, 5, 6]:

Solution (Optimal)#

class Solution:
    def middleNode(self, head):
        # Fast/slow pointer — returns second middle for even-length lists
        slow = head        # tortoise: moves 1 step per iteration
        fast = head        # hare: moves 2 steps per iteration
        while fast and fast.next:
            slow = slow.next             # advance slow by 1
            fast = fast.next.next        # advance fast by 2
        return slow                      # slow is at the middle when fast finishes

// Fast/slow pointer — single pass, O(1) extra space
var middleNode = function(head) {
    let slow = head;       // tortoise: 1 step at a time
    let fast = head;       // hare: 2 steps at a time
    while (fast && fast.next) {
        slow = slow.next;            // advance 1
        fast = fast.next.next;       // advance 2
    }
    return slow;           // slow points at the middle when the loop exits
};

Time: O(n) — slow visits exactly n/2 + 1 nodes Space: O(1) — only two pointer variables regardless of list length

Common Mistakes#

• Starting fast = head.next when you want the second middle — that subtle shift returns the first middle instead
• Using while fast.next and fast.next.next when the spec asks for the second middle — same loop body, wrong landing position
• Checking only fast.next in the condition — null pointer exception when fast itself is None on empty list
• Returning slow.val instead of the node slow — the spec asks for the node reference
• Assuming the loop runs at least once — a single-node list exits immediately with slow = head, which is correct

Interview Tips#

• State which middle you are returning before writing the loop — interviewers grade clarity here
• Mention the alternative one-line change for first-middle behavior even if not asked
• Bring up the relationship to nth-from-end (gap of k) and cycle detection (same condition, different work in body)
• Avoid the "count then walk" approach unless explicitly asked — it shows weaker pattern fluency
• Point out that this template generalizes to splitting a list into halves for merge sort

Follow-up Questions#

• What if you need the first middle for an even-length list? Hint: change condition to while fast.next and fast.next.next.
• Can you do this without modifying the list? Hint: yes — the algorithm only moves pointer variables, never next fields.
• How does this generalize to finding the node k steps from the end? Hint: maintain a gap of k between fast and slow.
• What if the list has a cycle? Hint: fast never reaches None — you must detect the cycle first with Floyd's.
• Can you split the list into two halves for merge sort with this template? Hint: cut after the first middle.

Key Takeaways#

• Fast moves 2x, slow moves 1x — when fast ends, slow is at the midpoint
• The exact middle (first vs second) depends only on the loop condition, not the body
• while fast and fast.next lands slow on the second middle for even-length lists
• while fast.next and fast.next.next lands slow on the first middle (used in palindrome / merge sort split)
• The same fast/slow primitive solves cycle detection, nth-from-end, and palindrome checking
• Always check fast before fast.next in the condition to avoid null dereference
• Memorize both variants — interviewers swap between them as a fluency check