What is the brute force approach and complexity for Middle of the Linked List?

Store every node pointer in a vector, return v[n/2] with time complexity O(N) and space complexity O(N).

What is the optimal approach and complexity for Middle of the Linked List?

slow moves 1, fast moves 2; when fast hits the end, slow is the middle with optimal time complexity O(N) and space complexity O(1).

How do you identify the pattern for Middle of the Linked List?

Look for key signals in the prompt: "middle node" indicates We need the point halfway along a list whose length we don't know → one pointer at double speed.; "singly linked list" indicates No indexes and no going back, so we can't jump to n / 2. We must find it while walking forward.; "two middles → return the second" indicates This decides the loop condition: `fast && fast->next` stops on the second middle..

Middle of the Linked List

Easy·LeetCode #876Basic Anchor

LeetCode

Jump:

30-Second Mental ModelLinked List — Fast & Slow (middle)

Complexity:O(N)→O(N)

Key Insight

Start two pointers at the head. Each round, slow moves 1 step and fast moves 2 steps. Fast always has walked exactly twice as far as slow. So when fast runs out of list, slow is exactly halfway — the middle — in a single pass.

Core Validity Invariant

Fast is always twice as far from the head as slow, so the moment fast reaches the end, slow is at position n / 2 — the middle.

Problem

You are given the head of a singly linked list. Return the middle node of the list.

If the list has an even number of nodes, there are two middle nodes. Return the second one.

Return the node itself (the list from that node onward), not just its value.

Input

head, the first node of a singly linked list.

Output

The middle node. For an even length, the second of the two middle nodes.

Example 1

Input: head = [1, 2, 3, 4, 5]

Output: [3, 4, 5]

5 nodes, so the middle is the 3rd node (value 3). The answer is printed as the list starting from it.

Example 2

Input: head = [1, 2, 3, 4, 5, 6]

Output: [4, 5, 6]

6 nodes, so the two middles are 3 and 4. We return the second one, 4.

Constraints

• The list has between 1 and 100 nodes.
• 1 ≤ Node.val ≤ 100

First, think yourself

Before opening any solution, try to answer these on paper. Use hints only when stuck — each hint is counted.

1.
In an array I would just return a[n / 2]. What stops me from doing that in a linked list?
2.
Do I know the length of the list before I start walking?
3.
If I counted the length first, how many steps from the head would the middle be?
4.
Can two pointers moving at different speeds tell me when I am halfway?
5.
For 6 nodes, should I stop on the 3rd node or the 4th? What about 5 nodes?

Brute force approach

Idea

A linked list can't jump to position n / 2, but an array can. So walk the list once, push every node pointer into a vector, then return v[n / 2].

Thinking process

1
If this were an array, the answer would be a[n / 2].
2
The only problem is that a linked list has no indexes.
3
So copy the node pointers into a vector. Now I have indexes again.
4
Check n / 2 on both cases: 5 / 2 = 2 → the 3rd node. 6 / 2 = 3 → the 4th node, which is the second middle. Correct.

Code & Implementation

brute.cpp

class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        // Copy every node pointer into an array, so we can jump to any position.
        vector<ListNode*> nodes;
        for (ListNode* cur = head; cur != nullptr; cur = cur->next) {
            nodes.push_back(cur);
        }
        // n / 2 is the middle for odd n, and the SECOND middle for even n.
        return nodes[nodes.size() / 2];
    }
};

import java.util.ArrayList;
import java.util.List;

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) {
        // Copy every node pointer into an array, so we can jump to any position.
        List<ListNode> nodes = new ArrayList<>();
        for (ListNode cur = head; cur != null; cur = cur.next) {
            nodes.add(cur);
        }
        // n / 2 is the middle for odd n, and the SECOND middle for even n.
        return nodes.get(nodes.size() / 2);
    }
}

from typing import Optional, List, Dict, Set, Tuple

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]:
        # Copy every node pointer into an array, so we can jump to any position.
        nodes: List[ListNode] = []
        cur = head
        while cur is not None:
            nodes.append(cur)
            cur = cur.next

        # n // 2 is the middle for odd n, and the SECOND middle for even n.
        return nodes[len(nodes) // 2]

export class ListNode {
    val: number;
    next: ListNode | null;
    constructor(val?: number, next?: ListNode | null) {
        this.val = (val === undefined ? 0 : val);
        this.next = (next === undefined ? null : next);
    }
}

export function middleNode(head: ListNode | null): ListNode | null {
    // Copy every node pointer into an array, so we can jump to any position.
    const nodes: ListNode[] = [];
    for (let cur = head; cur !== null; cur = cur.next) {
        nodes.push(cur);
    }
    // n / 2 is the middle for odd n, and the SECOND middle for even n.
    return nodes[Math.floor(nodes.length / 2)];
}

Complexity

Time O(N)Space O(N)

One pass, but the vector holds all n pointers. Store the pointers, not the values, because we must return the node itself.

Better approach

Why brute force is slow

It is already O(N) time, but it keeps n pointers in memory just to read one of them.

What repeated work are we doing?

We store the position of every node when we only need to know how far the middle is from the head.

What information can we reuse?

Keep only the count n. A second walk of n / 2 steps from the head lands on the middle, with O(1) extra memory.

New approach

Idea

We only needed the vector to reach position n / 2. We can reach it by walking instead: first count the nodes, then start again at the head and take n / 2 steps.

Thinking process

1
The vector stores all n pointers, but we only ever use one of them.
2
What we really need from the first pass is just the number n.
3
With n known, walk n / 2 steps from the head. That node is the middle.

Code & Implementation

better.cpp

class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        // Pass 1: count the nodes.
        int n = 0;
        for (ListNode* cur = head; cur != nullptr; cur = cur->next) {
            n++;
        }
        // Pass 2: walk n / 2 steps from the head.
        ListNode* cur = head;
        for (int i = 0; i < n / 2; i++) {
            cur = cur->next;
        }
        return cur;
    }
};

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) {
        // Pass 1: count the nodes.
        int n = 0;
        for (ListNode cur = head; cur != null; cur = cur.next) {
            n++;
        }
        // Pass 2: walk n / 2 steps from the head.
        ListNode cur = head;
        for (int i = 0; i < n / 2; i++) {
            cur = cur.next;
        }
        return cur;
    }
}

from typing import Optional, List, Dict, Set, Tuple

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]:
        # Pass 1: count the nodes.
        n = 0
        cur = head
        while cur is not None:
            n += 1
            cur = cur.next

        # Pass 2: walk n // 2 steps from the head.
        cur = head
        for _ in range(n // 2):
            cur = cur.next

        return cur

export class ListNode {
    val: number;
    next: ListNode | null;
    constructor(val?: number, next?: ListNode | null) {
        this.val = (val === undefined ? 0 : val);
        this.next = (next === undefined ? null : next);
    }
}

export function middleNode(head: ListNode | null): ListNode | null {
    // Pass 1: count the nodes.
    let n = 0;
    for (let cur = head; cur !== null; cur = cur.next) {
        n++;
    }
    // Pass 2: walk n / 2 steps from the head.
    let cur = head;
    for (let i = 0; i < Math.floor(n / 2); i++) {
        cur = cur!.next;
    }
    return cur;
}

Complexity

Time O(N)Space O(1)

About n + n/2 steps over two passes. Fine here, but it needs to walk the list twice.

Optimized approach

Idea

Start from brute force

Brute force stores every node just to read the one at position n / 2. The count-then-walk version drops the memory but walks the list one and a half times.

Find the repeated work

Counting the length and then walking to the middle are two walks over the same nodes. The second walk covers ground the first one already passed.

Define the state — what variables do I need?

slow: Moves 1 node per round. After k rounds it is at position k.
fast: Moves 2 nodes per round. After k rounds it is at position 2k (or null if it ran off the end).

Define validity

Fast is always twice as far from the head as slow, so the moment fast reaches the end, slow is at position n / 2 — the middle.

Define the transitions — when does each pointer move, and why is it safe?

fast != nullptr && fast->next != nullptr

slow = slow->next; fast = fast->next->next

fast has at least two more nodes to step on, so both moves are safe, and the 2 : 1 ratio is kept.

fast == nullptr (even length) or fast->next == nullptr (odd length)

stop and return slow

Odd n: fast is on the last node (position n − 1), so slow is at (n − 1) / 2, the exact middle. Even n: fast stepped past the end to position n, so slow is at n / 2, the second middle.

What does the current window add to the answer?

There is no running answer to update. The answer is simply wherever slow is standing when fast runs out of list.

Code & Implementation

optimal.cpp

class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        ListNode* slow = head;
        ListNode* fast = head;
        // fast moves 2 steps for every 1 step of slow,
        // so when fast runs off the end, slow has covered half the list.
        // Check fast first: fast->next is only safe once we know fast is not null.
        while (fast != nullptr && fast->next != nullptr) {
            slow = slow->next;
            fast = fast->next->next;
        }
        return slow;   // the second middle when the length is even
    }
};

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 for every 1 step of slow,
        // so when fast runs off the end, slow has covered half the list.
        // Check fast first: fast.next is only safe once we know fast is not null.
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow; // the second middle when the length is even
    }
}

from typing import Optional, List, Dict, Set, Tuple

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 for every 1 step of slow,
        # so when fast runs off the end, slow has covered half the list.
        # Check fast first: fast.next is only safe once we know fast is not null.
        while fast is not None and fast.next is not None:
            slow = slow.next
            fast = fast.next.next

        return slow  # the second middle when the length is even

export class ListNode {
    val: number;
    next: ListNode | null;
    constructor(val?: number, next?: ListNode | null) {
        this.val = (val === undefined ? 0 : val);
        this.next = (next === undefined ? null : next);
    }
}

export function middleNode(head: ListNode | null): ListNode | null {
    let slow = head;
    let fast = head;
    // fast moves 2 steps for every 1 step of slow,
    // so when fast runs off the end, slow has covered half the list.
    // Check fast first: fast.next is only safe once we know fast is not null.
    while (fast !== null && fast.next !== null) {
        slow = slow!.next;
        fast = fast.next.next;
    }
    return slow; // the second middle when the length is even
}

Complexity

Time O(N)Space O(1)

About n / 2 rounds. Each round moves fast 2 steps, so the list is walked once in total.

Why does this algorithm work?

Dry run

All approaches compared

Approach	Idea	Time	Space
Brute Force	Store every node pointer in a vector, return v[n/2]	O(N)	O(N)
Better	Pass 1 counts n, pass 2 walks n/2 steps; no extra memory	O(N)	O(1)
Optimal	slow moves 1, fast moves 2; when fast hits the end, slow is the middle	O(N)	O(1)

Why does this belong to this pattern?

Clues in the problem statement

“middle node”We need the point halfway along a list whose length we don't know → one pointer at double speed.
“singly linked list”No indexes and no going back, so we can't jump to n / 2. We must find it while walking forward.
“two middles → return the second”This decides the loop condition: `fast && fast->next` stops on the second middle.

singly linked list+position defined by a fraction of the length (half)+one pass, O(1) space→Linked List — Fast & Slow (middle)

This is the anchor of the Middle / split sub-pattern. Fast moves 2, slow moves 1, so when fast reaches the end, slow is halfway. Unlike cycle detection, there is no loop here: fast does reach null, and the only question is where slow is when it does. The next questions use this exact loop as a first step: to cut the list in half (palindrome, twin sum) or to stop one node early (delete the middle).

Don't make this mistake

Returning the first middle on an even length

✗ while (fast->next != nullptr && fast->next->next != nullptr) { slow = slow->next; fast = fast->next->next; }

✓ while (fast != nullptr && fast->next != nullptr) { slow = slow->next; fast = fast->next->next; }

The "wrong" loop stops one round early on even lengths. On [1, 2, 3, 4, 5, 6] it returns 3, but this problem wants the second middle, 4. Both loops are useful — the first-middle version is what you want when splitting a list into two halves (see the next questions) — but read which middle the problem asks for.

Checking fast->next before fast

✗ while (fast->next != nullptr && fast != nullptr)

✓ while (fast != nullptr && fast->next != nullptr)

On an even length, fast jumps to null. The wrong order then reads fast->next on a null pointer and crashes. && checks left to right, so put the null check first.

Storing values instead of nodes

✗ vector<int> vals; ... return new ListNode(vals[n / 2]);

✓ vector<ListNode*> nodes; ... return nodes[n / 2];

The answer is the node that is already in the list, with the rest of the list after it. A new node with the same value has no next, so the output would be [3] instead of [3, 4, 5].

Using the cycle-detection loop

✗ slow = head; fast = head->next; while (slow != fast) { ... }

Pattern confusion: in cycle detection we wait for fast to meet slow. Here there is no cycle, so they never meet and fast runs off the end. For the middle, the stop signal is fast reaching the end, not fast catching slow. Also, starting fast one node ahead changes which middle you land on.

Want to implement this?

Write it yourself on LeetCode, then come back and compare your code with the solutions above.

Open coding workspace

How did it go?

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Linked List — Fast & Slow translate into production architectures and low-level memory mechanics.

LLD Architecture