876. Middle of the Linked List

876

EasyLinked Lists and Pointer ManipulationSlow/fast pointersTortoise and hare midpoint

Middle of the Linked List

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

Open official problem prompt ↗

In plain English

Return the middle node of a singly linked list in one pass, preferring the second middle when the length is even.

Picture it like this

Two runners on a track starting together; the faster runs twice as fast, so when they reach the finish the slower runner is exactly at the halfway marker.

Example

Input: head = [1,2,3,4,5]
Output: [3,4,5]
Why: The list has 5 nodes, so the middle is the 3rd node (value 3); returning it yields the sublist 3 -> 4 -> 5.

Constraints

The number of nodes is in the range [1, 100]1 <= Node.val <= 100

Pattern lesson

See the pattern, then code

Tortoise and hare midpoint

↗

Linked Lists and Pointer Manipulation

Reversal, cycle detection, merging, reordering, or O(1)-space sequence edits.. If one pointer moves one step while another moves two steps, the slow pointer travels exactly half as far. When the fast pointer reaches the end, the slow pointer is at the middle. Choosing the loop condition carefully makes it land on the second middle for even lengths.

New words, made simpleKnow these before the algorithm

Tortoise and hare: A two-pointer scheme where one pointer advances twice as fast as the other.
Midpoint: The center node; for even counts the problem defines it as the second of the two central nodes.
Single pass: Solving with one traversal rather than counting length first and walking again.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Count then walk

Correct but takes two passes and is easier to get off-by-one.

Traverse once to count n, then walk n // 2 steps to reach the middle.

Time O(n)Space O(1)

Best choiceSlow/fast pointers

One clean pass with no length counting and the correct even-length behavior built in.

Move slow by one and fast by two; slow ends on the middle when fast finishes.

Time O(n)Space O(1)

The rule we keep true

Invariant

At the start of each loop iteration, fast has advanced exactly twice as many nodes as slow, so slow is always at the halfway point of the portion traversed so far.

Why this is correct

Reasoning

Because fast covers two nodes per step and slow covers one, slow's distance from the head is always half of fast's. The condition `while fast and fast.next` stops slow at index n // 2 (0-based), which is the middle for odd n and the second middle for even n, exactly matching the problem's requirement.

The algorithm in three movesSay these aloud before coding

1Start slow and fast at the head

slow=1 fast=1

2Advance slow by one and fast by two each iteration

slow=2 fast=3

3Stop when fast is null or fast.next is null

slow=3 fast=5 -> stop

4Return slow, which now points at the middle node

return node 3

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

1 · Read[1,2,3,4,5]

2 · AskSet both pointers

3 · Update stateslow=1, fast=1

4 · ResultEnter loop

Key takeaway

The slow pointer lands on node 3 exactly when the fast pointer reaches the last node.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 3Initialize both pointers
Both start at head so their relative speeds create the exact 2:1 distance ratio.
2
Lines 4-6Advance at two speeds
Checking fast and fast.next avoids dereferencing None; slow moves one and fast moves two each step.
3
Lines 7Return the middle
When the loop exits, slow sits on index n // 2, which is the (second) middle node.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

Single node returns that node
Two nodes returns the second node (the defined second middle)
Odd length returns the exact center
Even length returns the second of the two centers

Common beginner mistakes

Using `while fast.next and fast.next.next` returns the first middle for even lengths, contradicting the spec
Forgetting to check fast before fast.next risks a None dereference at the end
Advancing slow after fast within a mismatched order can shift the result by one node

Check your understanding

For an even-length list like [1,2,3,4], why does this code return node 3 and not node 2?

Middle of the Linked List

Middle of the Linked List

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Linked Lists and Pointer Manipulation