Abstract / Summary

Given only the middle node of a singly linked list, remove it without access to the head or previous node.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 61% (1+ million submissions).

Typical patterns to solve this problem:

• Linked List
• Two Pointers

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided Solution class implements a method deleteMiddle that removes the middle node from a singly-linked list. The algorithm first determines the length of the list, computes the index of the middle node, and then adjusts the links to exclude that node. Special handling is included for empty lists and lists where the middle node is the head.

Step-by-Step Execution

Handling an empty list

if not head:
    return None

When the input head is None, the function immediately returns None. This prevents any further processing on a non-existent list and ensures that the function’s contract of returning a list head is respected even for the empty case.

Counting the number of nodes

size = 0
last = head
while last:
    last = last.next
    size += 1

A traversal walks through the list once, incrementing size for each node encountered. The variable last progresses until it becomes None, at which point size holds the total number of nodes. This linear scan establishes the basis for locating the middle position.

Determining the middle index

mid = size // 2

Integer division yields the index of the node that should be removed. For an even number of nodes, the definition of “middle” follows the convention of removing the node at size // 2, which corresponds to the second of the two central nodes.

Removing the head when it is the middle

if mid == 0:
    return head.next

If the list contains only one node (size == 1), mid becomes 0. In this situation the head itself is the middle node, and the function returns head.next, which is None. This also covers the case of a two-node list where the second node is considered the middle, because size // 2 yields 1 and the subsequent logic will handle it correctly.

Traversing to the node preceding the middle

prev = head
while mid > 1:
    prev = prev.next
    mid -= 1

Starting from the head, the loop advances prev until it points to the node immediately before the one to be deleted. The loop condition mid > 1 ensures that exactly mid-1 steps are taken, positioning prev correctly for the link adjustment.

Skipping over the middle node

prev.next = prev.next.next

Once prev is positioned, its next reference is redirected to bypass the middle node, linking directly to the node that follows the middle. This effectively removes the middle node from the list without requiring additional memory.

Returning the possibly modified head

return head

After the deletion, the original head (or the new head if the original was removed) is returned, completing the operation.

Edge Cases Addressed

The implementation gracefully handles several boundary conditions:

• An empty input list results in an immediate None return.
• A single-node list triggers the mid == 0 branch, returning None because the sole node is removed.
• A two-node list leads to mid == 1; the traversal loop does not execute, and the link adjustment removes the second node, leaving the first node as the new list.
• Larger lists follow the general path of counting, computing the middle index, and relinking, ensuring correct removal regardless of odd or even length.

Performance Optimizations

The algorithm performs exactly two passes over the list: one to count nodes and a second to locate the predecessor of the middle node. This approach avoids the need for auxiliary data structures, keeping the memory footprint minimal. The early return when mid == 0 eliminates the second traversal for single-node lists, saving time in that scenario. Using integer division (//) provides a fast calculation of the middle index without additional conditional logic. Overall, the method achieves the deletion with linear time relative to the list length while maintaining constant extra space.

Imagine a long train where each car is connected to the one behind it, like a giant snake made of boxes. To find the middle of this train, the code first walks from the front all the way to the back to count just how many cars there are. Once the total count is known, the code divides that number by two to figure out exactly which car is sitting in the center.

If the train only has one car, the middle is the start, so the train just leaves empty. If the middle is further back, the code walks along the train again, stopping just one car before the middle one. Then, a little magic happens. The code tells the car right before the middle one to disconnect from the middle car and instead link directly to the one that comes after it. By skipping over that middle car, it disappears from the line, and the train stays connected as one single piece.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: linear
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Java	Python						TS
	WalkCCC	C++	Java	Python
	leetcode.ca	C++	Java	Python				Go	Rust	TS
	Progiez	C++	Java	Python
github	black-shadows	C++
	charles-wangkai		Java
	everthis				JS
	fartem						Ruby
	fsq	C++
	JoshCrozier				JS
	lkwq007			Python
	muhammadfarhankt							Go
	shreymehul					C#
	suxrobGM					C#
	trung-hn			Python
	varunu28		Java
	vthwang		Java
	withaarzoo	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, Rust, TypeScript
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fartem	Ruby
fsq	C++
JoshCrozier	JavaScript
lkwq007	Python
muhammadfarhankt	Go
shreymehul	C#
suxrobGM	C#
trung-hn	Python
varunu28	Java
vthwang	Java
withaarzoo	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality