Middle of the Linked List

EasyFast & Slow Pointers🧩 Fast & Slow Pointers LeetCode #876 ↗Updated Oct 30, 2026

Problem

Given the head of a non-empty singly linked list, return its middle node. When the length is even there are two middle candidates — return the second one (index n/2, 0-based).

Input[1,2,3,4,5]Output[3,4,5] (node 3)

Input[1,2,3,4,5,6]Output[4,5,6] (node 4)

1 ≤ n ≤ 100 · 1 ≤ Node.val ≤ 100

Try it yourself

Java

class Solution {
    public ListNode middleNode(ListNode head) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

Run two pointers from the head: fast takes 2 steps for every 1 step of slow. When fast falls off the end, slow has covered half the distance — it is the middle, found in one pass.

PatternFast & Slow Pointers

Instinct A next-step function you can follow (list nodes, digit-square sums, array-as-pointers) and you need a cycle, its entry, or the middle in O(1) space.

Memory hack Tortoise and hare - on a loop track the hare laps the tortoise; restart the tortoise at the gate and they meet at the loop's door.

Open the Fast & Slow Pointers guide →

Approaches

Brute ForceCopy Nodes to an Array

Time O(n)Space O(n)

A list has no random access, so build one: store every node in an ArrayList, then return nodes.get(n / 2). Integer division gives the second middle for even n automatically.

Java

public ListNode middleNode(ListNode head) {
    List<ListNode> nodes = new ArrayList<>();
    for (ListNode c = head; c != null; c = c.next) nodes.add(c);
    return nodes.get(nodes.size() / 2);
}

Trivial to write, but stores all n node references.

BetterCount, then Walk n/2 Steps

Time O(n)Space O(1)

First pass counts the nodes n. Second pass starts again at the head and advances exactly n/2 times. No extra memory, but the list is walked about 1.5 times.

Java

public ListNode middleNode(ListNode head) {
    int count = 0;
    for (ListNode c = head; c != null; c = c.next) count++;
    ListNode cur = head;
    for (int i = 0; i < count / 2; i++) cur = cur.next;
    return cur;
}

Constant space, but needs two passes over the list.

OptimalFast & Slow Pointers (Tortoise and Hare)

Time O(n)Space O(1)

Move slow 1 step and fast 2 steps while fast and fast.next exist. After t rounds slow is at index t and fast at 2t; the loop stops at t = ⌊n/2⌋ — the second middle.

Java

public ListNode middleNode(ListNode head) {
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;      // 1 step
        fast = fast.next.next; // 2 steps
    }
    return slow;
}

Dry run[1,2,3,4,5,6]

s slowf fast changed

start
1
s f
2

3

4

5

6

both at head
t=1
1

2
s
3
f
4

5

6

s+1, f+2
t=2
1

2

3
s
4

5
f
6

s+1, f+2
t=3
1

2

3

4
s
5

6

f=null → return 4 ✔

Single pass, O(1) memory, no length needed up front.

Pro tip

Want the first middle instead (e.g. to split for merge sort)? Loop while fast.next != null && fast.next.next != null.

At a glance

Level	Approach	Time	Space
Brute Force	Copy Nodes to an Array	`O(n)`	`O(n)`
Better	Count, then Walk n/2 Steps	`O(n)`	`O(1)`
Optimal	Fast & Slow Pointers (Tortoise and Hare)	`O(n)`	`O(1)`

Common pitfalls

Checking only fast.next — NPE when fast itself is null (even n).
Returning the first middle for even length when the second is required.
Starting fast at head.next silently shifts which middle you get.

Interview tips

Mention the count-then-walk idea, then upgrade to one pass with fast/slow.
Prove it: after t steps slow = t, fast = 2t, so slow is at half.
Note this is the first step of Palindrome List, Reorder List and list merge sort.

Pattern

Fast & slow pointers → middle, cycle detection or k-from-end in a single pass.

My notes saved in this browser