Delete the Middle Node of a Linked List

You are given the head of a singly linked list. Delete the middle node of the list and return the head of the modified list.

For a list of size n, the middle node is the node at index ⌊n / 2⌋ using 0-based indexing — where ⌊x⌋ is the largest integer less than or equal to x.

Concretely, for n = 1, 2, 3, 4, 5 the middle indices are 0, 1, 1, 2, 2. So in a list of 7 nodes the middle is index 3; in a list of 4 nodes it is index 2.

Deleting the only node of a single-element list leaves an empty list, so you return an empty (null) head.

Hints

· Stuck? Reveal one nudge at a time.

You must land on the node at index ⌊n/2⌋ — and to delete it in a singly linked list, what other node do you actually need a grip on?

One pointer moving twice as fast as another reaches the end in half the steps. Where is the slow one standing when the fast one stops?

Advance fast two steps and slow one step per loop, trailing slow with a prev pointer; when fast falls off the end, set prev.next = slow.next.

Common doubts

Because fast moves twice as far as slow. When fast has traveled the whole list of length n, slow has traveled n/2 — precisely index ⌊n/2⌋.

Its middle is index 0 — the node itself. Deleting it returns an empty (null) list, so guard this case before the loop.

Logically you only need to rewire prev.next past it. In languages with manual memory you may also free it; the judge only checks the resulting sequence of values.

Interview follow-ups

· What an interviewer asks next.

Give fast a k-step head start, then advance both until fast hits the end — slow lands on the target node's predecessor.

Same two speeds: if fast ever meets slow, there is a loop. This is Floyd's cycle-detection algorithm.

Fun facts

The two-speed idea is nicknamed the tortoise and the hare — the same racing metaphor Floyd used for his cycle-detection algorithm.
Finding the middle in one pass is the setup step for reversing the second half of a list, the standard trick for checking whether a linked list is a palindrome.

Asked at

AmazonMicrosoftGoogleMetaAdobe

Frequently Sometimes Occasionally

Example 1

Input: head = [1,3,4,7,1,2,6]
Output: [1,3,4,1,2,6]
n = 7, so the middle is index ⌊7/2⌋ = 3 (value 7). Removing it leaves [1,3,4,1,2,6].

Example 2

Input: head = [1,2,3,4]
Output: [1,2,4]
n = 4, so the middle is index ⌊4/2⌋ = 2 (value 3).

Example 3

Input: head = [2,1]
Output: [2]
n = 2, so the middle is index ⌊2/2⌋ = 1 (value 1). Only node 0 remains.

Constraints

- The number of nodes in the list is in the range [1, 10^5]. - 1 <= Node.val <= 10^5

Deleting the middle node looks trivial once you know where the middle is — the real skill is finding it in a single pass, without ever counting the list twice. This is your first taste of the fast-and-slow pointer trick that powers half of all linked-list interview questions.

Prerequisites

Before you start

· Concepts used directly in the solution.

Singly linked list traversal. Walking node by node with a pointer until you fall off the end at null.

Pointer rewiring. Deleting a node means pointing its predecessor's next past it.

Two-pointer technique. Two pointers moving at different speeds to locate a position in one sweep.

Clarifying questions

A minute of questions before you code shows you reason about guarantees and edge cases the way a senior engineer does.

Questions to ask first

· Signals seniority before you write a line of code.

Input validity

“Is the list guaranteed to be non-empty?”

The constraints promise at least one node, so I never receive a null head — but I still guard it defensively.

Edge cases

“What should I return if the list has exactly one node?”

Its middle is index 0, so deleting it leaves an empty list and I return null.

Constraints and scale

“How large can the list get?”

Up to 10^5 nodes, so an O(n) pass is fine — but I would rather not traverse the whole list twice if one pass suffices.

The ideal opening — say it like this

Before I code, let me confirm a couple of things.

The middle is floor of n over 2 with 0-based indexing, correct?

And a single-node list should come back empty, since its middle is the only node?

Understand the problem

Plain English: find the node at index ⌊n/2⌋, unlink it by connecting its predecessor to its successor, and return the head.

Worked example — head = [1,3,4,7,1,2,6]

index:  0   1   2   3   4   5   6
list:   1 → 3 → 4 → 7 → 1 → 2 → 6     n = 7,  middle = ⌊7/2⌋ = 3

remove index 3 (value 7):
        1 → 3 → 4 ──────→ 1 → 2 → 6
result: 1 → 3 → 4 → 1 → 2 → 6

Key observations

1Aha

You need the node BEFORE the middle, not the middle itself

In a singly linked list you can only detach a node through its predecessor. To delete index mid, keep a prev pointer trailing one step behind the middle, then set prev.next = prev.next.next.

2Aha

Two speeds turn two passes into one

Move fast two nodes for every one node slow moves. fast covers twice the distance, so when fast falls off the end, slow sits at ⌊n/2⌋ — the middle — with no counting required.

step   slow   fast
 0      0      0
 1      1      2
 2      2      4
 3      3      6     fast.next is null → stop, slow = 3 = middle

3Aha

The single-node list is the only real edge case

If head.next is null there is nothing after the head, its middle is index 0, and the answer is an empty list. Guard this up front and the main loop stays clean.

Brute force vs optimal

	Two pass (count then walk)	Fast & slow (one pass)
Passes over list	2	1
Time	O(n)	O(n)
Space	O(1)	O(1)

Both are linear, but the two-pointer method finds the middle in a single sweep — the version you want to reach for. See the full code in the Approaches selector below.

Summary

Key takeaway

To find the middle of a linked list in one pass, run a fast pointer at double speed; when it reaches the end, a slow pointer is at the middle. Keep a prev pointer trailing the slow pointer so you can unlink cleanly.

if head has no next: return null
slow = head, fast = head, prev = null
while fast and fast.next:
    prev = slow
    slow = slow.next
    fast = fast.next.next
prev.next = slow.next
return head