Loading…

easyLinked ListsLC #876Frequently asked

Middle of the Linked List

Q: How do you solve Middle of the Linked List using the Count-Then-Walk — Two Passes approach?

When to use it: Mention briefly as the obvious baseline that proves you understand the goal, then improve to one pass. The most direct reading of the problem: the middle is at index `n / 2`, so figure out `n`, then walk there. It splits naturally into two passes. **Why two passes are needed here.** Arrays expose their length for free, but a singly linked list does not — the only way to learn `n` is to walk to the end counting nodes. Once we have `n`, the second-middle index for the problem's convention is `n / 2` using integer division: for `n = 5` that's index `2` (node 3), and for `n = 6` that's index `3` (node 4), exactly the 'second middle' rule. **Why `n / 2` gives the second middle.** With zero-based indexing, an even list of length `n` has middles at indices `n/2 - 1` and `n/2`. Integer-dividing `n / 2` lands on the larger of the two — the second middle. For odd `n`, `n / 2` floors to the unique centre. So a single formula covers both parities, which is worth saying out loud. **Why we don't ship this.** It's correct and still O(n), but it traverses roughly 1.5n nodes and reads the list twice. Interviewers use this problem specifically to see whether you know the single-pass fast/slow technique, so this serves only as the springboard. **When it is actually preferable.** If you must find the middle repeatedly and can cache the length, or if you need the index for other reasons anyway, the explicit count is sometimes clearer. But as a standalone answer, lead with fast/slow. Time complexity: O(n). Space complexity: O(1).

LCPractice

Linked List · 9 of 24 · 8 min

Given the head of a singly linked list, return the middle node of the linked list.

If there are two middle nodes (the list has an even number of nodes), return the second middle node.

For example, for [1, 2, 3, 4, 5, 6] the two middles are 3 and 4, and you must return the node 4.

In plain English

We must return the middle node itself (the node, not just its value), and on even-length lists the tie is broken toward the second of the two centre nodes. The list length isn't given, so the elegant solution avoids a separate counting pass: by moving one pointer twice as fast as another, the slow pointer reaches the centre exactly when the fast pointer reaches the end.

Examples

Example 1

Input: head = [1, 2, 3, 4, 5]
Output: [3, 4, 5]
Note: Odd length 5 → single middle is node 3. The returned node is 3, whose sublist is [3, 4, 5].

Example 2

Input: head = [1, 2, 3, 4, 5, 6]
Output: [4, 5, 6]
Note: Even length 6 → two middles 3 and 4; return the second, node 4, whose sublist is [4, 5, 6].

Example 3

Input: head = [1]
Output: [1]
Note: Single node is its own middle. fast and fast.next are checked, loop never runs, slow stays at head.

Constraints

The number of nodes in the list is in the range [1, 100]
1 ≤ Node.val ≤ 100
The list is non-empty (at least one node)

Clarifying questions4First question: For an even-length list, do you want the first or the second middle node?Explore questions

Q1.For an even-length list, do you want the first or the second middle node?
LeetCode 876 wants the second. Starting both pointers at head gives the second middle naturally; I'll confirm this is what you expect before coding.
Q2.Can I make two passes — count the length, then walk to n/2?
I can, and it's O(n) too, but the one-pass fast/slow approach is cleaner and avoids re-walking. I'll lead with one pass.
Q3.Is the list guaranteed non-empty?
Yes, constraints say at least one node. If empty lists were possible I'd return null when head is null.
Q4.Return the node or its value?
Return the node — LeetCode expects the ListNode reference, and downstream problems (split, palindrome) need the node itself.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Use two pointers, slow and fast, both starting at head. Advance slow by one and fast by two each iteration. When fast falls off the end, slow is sitting exactly on the middle. Because the list length is unknown up front, this finds the middle in a single pass with O(1) extra space — no length count needed. For even-length lists this returns the second of the two middle nodes (LeetCode 876's requirement).

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you know the fast/slow two-pointer trick to find a midpoint in one pass without first counting the length, and whether you handle the loop guard so you never dereference a null fast pointer.

Where candidates slip

Using `while fast.next and fast.next.next` (returns the first middle) when the problem asks for the second, or writing `while fast` alone and crashing on `fast.next.next` for even-length lists.

How to stand out

Clarify which middle is expected for even lengths before coding, state that starting both pointers at head yields the second middle, and connect the tortoise/hare engine to cycle detection and palindrome checking.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Count-Then-Walk — Two Passes	`O(n)`	`O(1)`	Mention briefly as the obvious baseline that proves you understand the goal, then improve to one pass.	Read
2	Fast/Slow Pointers — Single Pass (Optimal)Optimal	`O(n)`	`O(1)`	Lead with this. Frame it as 'tortoise and hare: when the hare reaches the end, the tortoise is at the middle'.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewFind the middle of a linked listIs the length known up front?YesNoExplore the full tree

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Count-Then-Walk — Two Passes

TimeO(n)SpaceO(1)

Mention briefly as the obvious baseline that proves you understand the goal, then improve to one pass.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

If you knew the length n, the middle index is just n / 2 (integer division) for the second-middle convention. How do you get n from a list?

2Hint 2Explore hint

Walk the list once counting nodes to get n. Then walk again from head, stopping after n / 2 steps.

3Hint 3Explore hint

Two passes, both O(n), O(1) space. It works, but you traverse most of the list twice — the fast/slow trick does it in one pass.

A · Core idea

The most direct reading of the problem: the middle is at index n / 2, so figure out n, then walk there. It splits naturally into two passes.

Why two passes are needed here. Arrays expose their length for free, but a singly linked list does not — the only way to learn n is to walk to the end counting nodes. Once we have n, the second-middle index for the problem's convention is n / 2 using integer division: for n = 5 that's index 2 (node 3), and for n = 6 that's index 3 (node 4), exactly the 'second middle' rule.

Why `n / 2` gives the second middle. With zero-based indexing, an even list of length n has middles at indices n/2 - 1 and n/2. Integer-dividing n / 2 lands on the larger of the two — the second middle. For odd n, n / 2 floors to the unique centre. So a single formula covers both parities, which is worth saying out loud.

Why we don't ship this. It's correct and still O(n), but it traverses roughly 1.5n nodes and reads the list twice. Interviewers use this problem specifically to see whether you know the single-pass fast/slow technique, so this serves only as the springboard.

When it is actually preferable. If you must find the middle repeatedly and can cache the length, or if you need the index for other reasons anyway, the explicit count is sometimes clearer. But as a standalone answer, lead with fast/slow.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

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

pass 1

count nodes 1..6

Staten = 6

Final result[4, 5, 6]

C · Code with teaching comments

Reference implementation previewpublic class ListNode { int val; ListNode next; ListNode() {} ListNode(int val) { this.val = val; }Explore the full code

solution.javaJava

Count-Then-Walk — Two Passes — reference

3 teaching notes

1
public class ListNode {
2
    int val;
3
    ListNode next;
4
    ListNode() {}
5
    ListNode(int val) { this.val = val; }
6
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
7
}
8
 
9
public ListNode middleNode(ListNode head) {
10
    int n = 0;
11
    // First pass: walk the whole list to learn n, the only way to get a length from a
12
    // singly linked list.
13
    for (ListNode p = head; p != null; p = p.next) {
14
        n++;
15
    }
16
    ListNode curr = head;
17
    // Integer division n/2 targets the second middle on even lengths and the unique
18
    // centre on odd.
19
    for (int i = 0; i < n / 2; i++) {
20
        curr = curr.next;
21
    }
22
    // After n/2 advances, curr sits on the middle node.
23
    return curr;
24
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.24 lines

D · Why it works and complexityO(n) timeO(1) spaceOpen the invariant and proofExplore the proof

The n / 2 integer-division formula quietly encodes the 'second middle on even length' rule for free — recognising that one expression handles both parities is the takeaway from this baseline.

ComplexityO(n) time, O(1) space — First pass counts all n nodes; second pass walks n/2 nodes. Total ~1.5n steps = O(n) time, O(1) space (just a counter and a pointer).

E · Edge cases and pitfalls5head = [1] — n = 1, n/2 = 0 → zero advances, return head. Single node is its own middle.Explore edge cases

Edge cases handled

head = [1]n = 1, n/2 = 0 → zero advances, return head. Single node is its own middle.
head = [1, 2]n = 2, n/2 = 1 → one advance, return node 2 (the second middle).

Pitfalls

Using (n - 1) / 2 — that targets the FIRST middle, the wrong one for this problem.
Re-walking from the wrong start or off-by-one in the second loop.
Presenting this as the final answer instead of advancing to fast/slow.

03.2

Approach 2 of 2 · Optimal

Fast/Slow Pointers — Single Pass (Optimal)

TimeO(n)SpaceO(1)

Lead with this. Frame it as 'tortoise and hare: when the hare reaches the end, the tortoise is at the middle'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Imagine two runners on the list, one twice as fast as the other. When the fast one reaches the end, where is the slow one?

2Hint 2Explore hint

Start slow and fast at head. Each step: slow moves one node, fast moves two. The 2:1 ratio means slow covers half the distance fast does.

3Hint 3Explore hint

Loop while fast != null AND fast.next != null so fast.next.next is safe. When the loop ends, slow is on the middle — the second middle for even lengths.

A · Core idea

Two pointers leave the head together, but the fast one takes two steps for every one the slow one takes. By the time the fast pointer runs off the end of the list, the slow pointer — having moved at half the speed — is exactly halfway, which is the middle.

Why the 2:1 ratio lands slow on the middle. Distance is speed × time. Over the same number of iterations, fast travels twice as far as slow. When fast has traveled the full length n (reaching the end), slow has traveled n / 2 — the middle index. There's no arithmetic to do and no length to compute; the relative speed is the computation. This is why it's one pass instead of the count-then-walk's one-and-a-half.

Why the loop guard is `fast and fast.next`. Each iteration does fast = fast.next.next, which dereferences two links ahead. For that to be safe, both fast and fast.next must be non-null. Checking only fast crashes on even-length lists: when fast lands on the last node, fast.next is null and fast.next.next throws. Checking both stops the loop one step earlier and keeps the dereference legal.

Why this returns the second middle on even lengths. Trace [1,2,3,4,5,6]. Start: slow=1, fast=1. Iter1: slow=2, fast=3. Iter2: slow=3, fast=5. Iter3: slow=4, fast=null (5.next.next). Loop ends with slow=4 — the second of the two middles (3 and 4). Because both pointers begin at head, the geometry naturally favours the later middle, which is precisely what LeetCode 876 demands. If the problem wanted the first middle, you'd start fast one node ahead or loop while fast.next and fast.next.next.

Why for odd lengths it lands on the single centre. Trace [1,2,3,4,5]. Iter1: slow=2, fast=3. Iter2: slow=3, fast=5. Now fast.next is null, loop ends, slow=3 — the unique centre. The same code handles both parities with no branching.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

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

Array state

start

slow=1, fast=1

slow ↓fast ↓

[0]

[1]

[2]

[3]

[4]

[5]

Current pointerResolved stateNot processed

Final result[4, 5, 6]

C · Code with teaching comments

solution.javaJava

Fast/Slow Pointers — Single Pass (Optimal) — optimal

6 teaching notes

1
public ListNode middleNode(ListNode head) {
2
    // Tortoise starts at head; it ends on the middle node.
3
    ListNode slow = head;
4
    // Hare also starts at head — this is what yields the SECOND middle on even lengths.
5
    ListNode fast = head;
6
    // Both checks guard the two-link jump on the next line; checking only fast crashes
7
    // on even lengths.
8
    while (fast != null && fast.next != null) {
9
        // Tortoise advances one node — half the hare's speed.
10
        slow = slow.next;
11
        // Hare advances two nodes; when it runs off the end, slow is halfway.
12
        fast = fast.next.next;
13
    }
14
    // Loop exit means fast finished, so slow is on the middle.
15
    return slow;
16
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.16 lines

D · Why it works and complexityO(n) timeO(1) spaceOpen the invariant and proofExplore the proof

The relative speed between two pointers encodes a computation for free: a 2:1 ratio computes 'halfway', which is why no length count is needed. This insight generalises — a 1-step gap of k finds the kth-from-end (Remove Nth Node), and equal speed on a cycle guarantees a meeting (Linked List Cycle). One engine, many midpoint/cycle problems.

ComplexityO(n) time, O(1) space — fast traverses the whole list once (≈ n/2 iterations, each advancing fast by two), and slow advances by one per iteration. One pass total → O(n) time, O(1) space (two pointers).

E · Edge cases and pitfalls7head = [1] — fast=head, fast.next is null → loop never runs, return slow=head. A single node is its own middle.Explore edge cases

Edge cases handled

head = [1]fast=head, fast.next is null → loop never runs, return slow=head. A single node is its own middle.
head = [1, 2]Iter1: slow→2, fast→null (2.next.next). Loop ends, return node 2 — the second middle.
head = [1, 2, 3]Iter1: slow→2, fast→3. fast.next null → stop. Return node 2, the unique centre of an odd list.

Pitfalls

Writing `while (fast != null)` only — crashes on `fast.next.next` for even-length lists.
Starting fast at head.next when the problem wants the second middle — that yields the first middle.
Advancing slow by two or fast by one by mistake — breaks the 2:1 ratio that defines the midpoint.
Returning slow.val when the problem asks for the node.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic ListNode middleNode(ListNode head) { ListNode slow = head; ListNode fast = head; while (fast != null && fast.next != null) { slow = slow.next;Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Missing the fast.next null check

On even-length lists fast eventually lands on the last node, where fast.next is null. Evaluating fast.next.next then dereferences null and crashes.

Explore the code comparison

Don't write this

while (fast != null) {
    slow = slow.next;
    fast = fast.next.next; // NPE when fast is the last node
}

Write this instead

while (fast != null && fast.next != null) {
    slow = slow.next;
    fast = fast.next.next;
}

Returning the first middle instead of the second

LeetCode 876 requires the second middle on even lengths. Looping on fast.next/fast.next.next or starting fast ahead lands slow on the first middle.

Explore the code comparison

Don't write this

slow = head
fast = head
while fast.next and fast.next.next:  # stops one step earlier
    slow = slow.next
    fast = fast.next.next
return slow   # this is the FIRST middle

Write this instead

slow = head
fast = head
while fast and fast.next:
    slow = slow.next
    fast = fast.next.next
return slow   # second middle, as required

Breaking the 2:1 speed ratio

The midpoint result depends entirely on fast moving exactly twice as fast as slow. Advancing fast by one (or slow by two) destroys the invariant.

Explore the code comparison

Don't write this

while fast and fast.next:
    slow = slow.next
    fast = fast.next      # only one step — fast is no longer 'fast'
return slow

Write this instead

while fast and fast.next:
    slow = slow.next
    fast = fast.next.next
return slow

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Fast/slow two-pointer (tortoise and hare) midpoint

Code pattern to memorize

slow = head
fast = head
while fast and fast.next:
    slow = slow.next
    fast = fast.next.next
return slow   # second middle when length is even

Rules to remember

1Both pointers start at head; fast moves twice as fast as slow, so slow lands at the midpoint when fast finishes.
2Loop condition is fast and fast.next — checking both prevents a null dereference on fast.next.next.
3Starting both at head returns the second middle on even lengths (1→2→3→4→5→6 returns 4). LeetCode 876 wants exactly this.
4To get the first middle instead, start fast at head.next, or loop while fast.next and fast.next.next.
5No length counting needed — the 2:1 speed ratio finds the middle in one pass, which is the whole point over the count-then-walk approach.
6This same slow/fast skeleton detects cycles and finds the kth-from-end — internalise the pointer-advance order.

Use this pattern when

Find the midpoint of a singly linked list without knowing its length
Split a list into two halves (merge sort on lists, reorder, palindrome check)
Any 'meet in the middle' or 'second-half' linked-list subproblem
Cycle detection or kth-from-end — same tortoise/hare machinery

Choose another pattern when

You already know the length (e.g. an array, or a length field) → just index to n/2
It's a doubly linked list with a tail pointer → walk inward from both ends
You need every node's index, not just the middle → a single counting pass is simpler

Interview takeaway

Fast/slow pointers turn 'find the middle without a length' into a single O(1)-space pass. The same two-pointer engine powers Linked List Cycle, Palindrome Linked List, and Reorder List — learn the advance order and the `fast and fast.next` guard once.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternCanonical fast/slow two-pointer midpoint. The 2:1-speed trick finds a midpoint in one O(1)-space pass and is the splitting step inside Palindrome Linked List, Reorder List, and merge sort on lists. The same engine with a different gap or equal speed solves Remove Nth Node and Linked List Cycle.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Palindrome Linked List
Find the middle with fast/slow, reverse the second half, then compare the two halves.
Linked List Cycle
Coming soon
Same tortoise/hare engine; if fast ever meets slow there is a cycle.
Remove Nth Node From End of List
Coming soon
Two pointers with a fixed gap of n instead of a 2:1 ratio finds the kth-from-end in one pass.
Reorder List
Split at the middle (fast/slow), reverse the second half, then interleave.

Same pattern

←

Add Two Numbers

Continue · Next problem

Palindrome Linked List

easyLinked ListsLC #876Frequently asked

Middle of the Linked List

LCPractice

Linked List · 9 of 24 · 8 min

Given the head of a singly linked list, return the middle node of the linked list.

If there are two middle nodes (the list has an even number of nodes), return the second middle node.

For example, for [1, 2, 3, 4, 5, 6] the two middles are 3 and 4, and you must return the node 4.

In plain English

Examples

Example 1

Input: head = [1, 2, 3, 4, 5]
Output: [3, 4, 5]
Note: Odd length 5 → single middle is node 3. The returned node is 3, whose sublist is [3, 4, 5].

Example 2

Input: head = [1, 2, 3, 4, 5, 6]
Output: [4, 5, 6]
Note: Even length 6 → two middles 3 and 4; return the second, node 4, whose sublist is [4, 5, 6].

Example 3

Input: head = [1]
Output: [1]
Note: Single node is its own middle. fast and fast.next are checked, loop never runs, slow stays at head.

Constraints

The number of nodes in the list is in the range [1, 100]
1 ≤ Node.val ≤ 100
The list is non-empty (at least one node)

Clarifying questions4First question: For an even-length list, do you want the first or the second middle node?Explore questions

Q1.For an even-length list, do you want the first or the second middle node?
LeetCode 876 wants the second. Starting both pointers at head gives the second middle naturally; I'll confirm this is what you expect before coding.
Q2.Can I make two passes — count the length, then walk to n/2?
I can, and it's O(n) too, but the one-pass fast/slow approach is cleaner and avoids re-walking. I'll lead with one pass.
Q3.Is the list guaranteed non-empty?
Yes, constraints say at least one node. If empty lists were possible I'd return null when head is null.
Q4.Return the node or its value?
Return the node — LeetCode expects the ListNode reference, and downstream problems (split, palindrome) need the node itself.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you know the fast/slow two-pointer trick to find a midpoint in one pass without first counting the length, and whether you handle the loop guard so you never dereference a null fast pointer.

Where candidates slip

Using `while fast.next and fast.next.next` (returns the first middle) when the problem asks for the second, or writing `while fast` alone and crashing on `fast.next.next` for even-length lists.

How to stand out

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Count-Then-Walk — Two Passes	`O(n)`	`O(1)`	Mention briefly as the obvious baseline that proves you understand the goal, then improve to one pass.	Read
2	Fast/Slow Pointers — Single Pass (Optimal)Optimal	`O(n)`	`O(1)`	Lead with this. Frame it as 'tortoise and hare: when the hare reaches the end, the tortoise is at the middle'.	Read

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Count-Then-Walk — Two Passes

TimeO(n)SpaceO(1)

Mention briefly as the obvious baseline that proves you understand the goal, then improve to one pass.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

If you knew the length n, the middle index is just n / 2 (integer division) for the second-middle convention. How do you get n from a list?

2Hint 2Explore hint

Walk the list once counting nodes to get n. Then walk again from head, stopping after n / 2 steps.

3Hint 3Explore hint

Two passes, both O(n), O(1) space. It works, but you traverse most of the list twice — the fast/slow trick does it in one pass.

A · Core idea

The most direct reading of the problem: the middle is at index n / 2, so figure out n, then walk there. It splits naturally into two passes.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

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

pass 1

count nodes 1..6

Staten = 6

Final result[4, 5, 6]

C · Code with teaching comments

Reference implementation previewpublic class ListNode { int val; ListNode next; ListNode() {} ListNode(int val) { this.val = val; }Explore the full code

solution.javaJava

Count-Then-Walk — Two Passes — reference

3 teaching notes

1
public class ListNode {
2
    int val;
3
    ListNode next;
4
    ListNode() {}
5
    ListNode(int val) { this.val = val; }
6
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
7
}
8
 
9
public ListNode middleNode(ListNode head) {
10
    int n = 0;
11
    // First pass: walk the whole list to learn n, the only way to get a length from a
12
    // singly linked list.
13
    for (ListNode p = head; p != null; p = p.next) {
14
        n++;
15
    }
16
    ListNode curr = head;
17
    // Integer division n/2 targets the second middle on even lengths and the unique
18
    // centre on odd.
19
    for (int i = 0; i < n / 2; i++) {
20
        curr = curr.next;
21
    }
22
    // After n/2 advances, curr sits on the middle node.
23
    return curr;
24
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.24 lines

D · Why it works and complexityO(n) timeO(1) spaceOpen the invariant and proofExplore the proof

The n / 2 integer-division formula quietly encodes the 'second middle on even length' rule for free — recognising that one expression handles both parities is the takeaway from this baseline.

ComplexityO(n) time, O(1) space — First pass counts all n nodes; second pass walks n/2 nodes. Total ~1.5n steps = O(n) time, O(1) space (just a counter and a pointer).

E · Edge cases and pitfalls5head = [1] — n = 1, n/2 = 0 → zero advances, return head. Single node is its own middle.Explore edge cases

Edge cases handled

head = [1]n = 1, n/2 = 0 → zero advances, return head. Single node is its own middle.
head = [1, 2]n = 2, n/2 = 1 → one advance, return node 2 (the second middle).

Pitfalls

Using (n - 1) / 2 — that targets the FIRST middle, the wrong one for this problem.
Re-walking from the wrong start or off-by-one in the second loop.
Presenting this as the final answer instead of advancing to fast/slow.

03.2

Approach 2 of 2 · Optimal

Fast/Slow Pointers — Single Pass (Optimal)

TimeO(n)SpaceO(1)

Lead with this. Frame it as 'tortoise and hare: when the hare reaches the end, the tortoise is at the middle'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Imagine two runners on the list, one twice as fast as the other. When the fast one reaches the end, where is the slow one?

2Hint 2Explore hint

Start slow and fast at head. Each step: slow moves one node, fast moves two. The 2:1 ratio means slow covers half the distance fast does.

3Hint 3Explore hint

Loop while fast != null AND fast.next != null so fast.next.next is safe. When the loop ends, slow is on the middle — the second middle for even lengths.

A · Core idea

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

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

Array state

start

slow=1, fast=1

slow ↓fast ↓

[0]

[1]

[2]

[3]

[4]

[5]

Current pointerResolved stateNot processed

Final result[4, 5, 6]

C · Code with teaching comments

solution.javaJava

Fast/Slow Pointers — Single Pass (Optimal) — optimal

6 teaching notes

1
public ListNode middleNode(ListNode head) {
2
    // Tortoise starts at head; it ends on the middle node.
3
    ListNode slow = head;
4
    // Hare also starts at head — this is what yields the SECOND middle on even lengths.
5
    ListNode fast = head;
6
    // Both checks guard the two-link jump on the next line; checking only fast crashes
7
    // on even lengths.
8
    while (fast != null && fast.next != null) {
9
        // Tortoise advances one node — half the hare's speed.
10
        slow = slow.next;
11
        // Hare advances two nodes; when it runs off the end, slow is halfway.
12
        fast = fast.next.next;
13
    }
14
    // Loop exit means fast finished, so slow is on the middle.
15
    return slow;
16
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.16 lines

D · Why it works and complexityO(n) timeO(1) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls7head = [1] — fast=head, fast.next is null → loop never runs, return slow=head. A single node is its own middle.Explore edge cases

Edge cases handled

head = [1]fast=head, fast.next is null → loop never runs, return slow=head. A single node is its own middle.
head = [1, 2]Iter1: slow→2, fast→null (2.next.next). Loop ends, return node 2 — the second middle.
head = [1, 2, 3]Iter1: slow→2, fast→3. fast.next null → stop. Return node 2, the unique centre of an odd list.

Pitfalls

Writing `while (fast != null)` only — crashes on `fast.next.next` for even-length lists.
Starting fast at head.next when the problem wants the second middle — that yields the first middle.
Advancing slow by two or fast by one by mistake — breaks the 2:1 ratio that defines the midpoint.
Returning slow.val when the problem asks for the node.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic ListNode middleNode(ListNode head) { ListNode slow = head; ListNode fast = head; while (fast != null && fast.next != null) { slow = slow.next;Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Missing the fast.next null check

On even-length lists fast eventually lands on the last node, where fast.next is null. Evaluating fast.next.next then dereferences null and crashes.

Explore the code comparison

Don't write this

while (fast != null) {
    slow = slow.next;
    fast = fast.next.next; // NPE when fast is the last node
}

Write this instead

while (fast != null && fast.next != null) {
    slow = slow.next;
    fast = fast.next.next;
}

Returning the first middle instead of the second

LeetCode 876 requires the second middle on even lengths. Looping on fast.next/fast.next.next or starting fast ahead lands slow on the first middle.

Explore the code comparison

Don't write this

slow = head
fast = head
while fast.next and fast.next.next:  # stops one step earlier
    slow = slow.next
    fast = fast.next.next
return slow   # this is the FIRST middle

Write this instead

slow = head
fast = head
while fast and fast.next:
    slow = slow.next
    fast = fast.next.next
return slow   # second middle, as required

Breaking the 2:1 speed ratio

The midpoint result depends entirely on fast moving exactly twice as fast as slow. Advancing fast by one (or slow by two) destroys the invariant.

Explore the code comparison

Don't write this

while fast and fast.next:
    slow = slow.next
    fast = fast.next      # only one step — fast is no longer 'fast'
return slow

Write this instead

while fast and fast.next:
    slow = slow.next
    fast = fast.next.next
return slow

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Fast/slow two-pointer (tortoise and hare) midpoint

Code pattern to memorize

slow = head
fast = head
while fast and fast.next:
    slow = slow.next
    fast = fast.next.next
return slow   # second middle when length is even

Rules to remember

1Both pointers start at head; fast moves twice as fast as slow, so slow lands at the midpoint when fast finishes.
2Loop condition is fast and fast.next — checking both prevents a null dereference on fast.next.next.
3Starting both at head returns the second middle on even lengths (1→2→3→4→5→6 returns 4). LeetCode 876 wants exactly this.
4To get the first middle instead, start fast at head.next, or loop while fast.next and fast.next.next.
5No length counting needed — the 2:1 speed ratio finds the middle in one pass, which is the whole point over the count-then-walk approach.
6This same slow/fast skeleton detects cycles and finds the kth-from-end — internalise the pointer-advance order.

Use this pattern when

Find the midpoint of a singly linked list without knowing its length
Split a list into two halves (merge sort on lists, reorder, palindrome check)
Any 'meet in the middle' or 'second-half' linked-list subproblem
Cycle detection or kth-from-end — same tortoise/hare machinery

Choose another pattern when

You already know the length (e.g. an array, or a length field) → just index to n/2
It's a doubly linked list with a tail pointer → walk inward from both ends
You need every node's index, not just the middle → a single counting pass is simpler

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Palindrome Linked List
Find the middle with fast/slow, reverse the second half, then compare the two halves.
Linked List Cycle
Coming soon
Same tortoise/hare engine; if fast ever meets slow there is a cycle.
Remove Nth Node From End of List
Coming soon
Two pointers with a fixed gap of n instead of a 2:1 ratio finds the kth-from-end in one pass.
Reorder List
Split at the middle (fast/slow), reverse the second half, then interleave.

Same pattern

←

Add Two Numbers

Continue · Next problem

Palindrome Linked List