15% off all plans & roadmaps Use code
See plansDelete the Middle Node of a Linked List
- LeetCode 2095
- Medium
- Two Pointers
- Fixed Separation (Nth Node from End)
Updated
TL;DR: You delete the middle node of a singly linked list and return the head. A slow pointer moves one step while a fast pointer moves two, so slow stops right before the middle node and can unlink it.
Problem
You are given the head of a linked list. Delete the middle node, and return the head of the modified linked list.
The middle node of a linked list of size n is the ⌊n / 2⌋-th node from the start, using 0-based indexing. Here ⌊x⌋ is the largest integer less than or equal to x. For n = 1, 2, 3, 4, and 5, the middle nodes are at indices 0, 1, 1, 2, and 2.
Example 1
Input: head = [1,3,4,7,1,2,6] Output: [1,3,4,1,2,6] Explanation: Since n = 7, the node at index 3 with value 7 is the middle node. Removing it leaves the list shown in the output.
Example 2
Input: head = [1,2,3,4] Output: [1,2,4] Explanation: For n = 4, the node at index 2 with value 3 is the middle node.
Example 3
Input: head = [2,1] Output: [2] Explanation: For n = 2, the node at index 1 with value 1 is the middle node. Only the node with value 2 remains.
Constraints
- The number of nodes in the list is in the range
[1, 10^5]. 1 <= Node.val <= 10^5
Constraints that matter
- With up to 10^5 nodes, a single linear pass is fine, but any walk from every node to find its predecessor is O(n^2) and too slow.
- The list is singly linked, so you cannot step backward. You must find the node before the middle in a forward walk, because deleting a node requires its predecessor.
- Node values go up to 10^5, but the values never affect the logic. Decide by position, never by value, so duplicates are handled correctly.
- A one-node list has no predecessor. Either handle that case directly or add a dummy node in front of the head.
Hints
Hint 1
This is a Two Pointers problem.
Hint 2
A beginner first counts the nodes, then walks the list again to the node before the middle.
Solution
Intuition
This is a Two Pointers problem. The middle of a list depends on its length, and the length is unknown at the start. Finding the length first means two passes. Two pointers moving at different speeds can find the middle in one pass, because the fast pointer reaches the end when the slow pointer is halfway.
Deletion adds a second requirement. A singly linked list lets you change next only from the node before the target, so the slow pointer must stop one node early. A dummy node placed before the head lets the same code handle the first node too, which matters when the list has only one node.
The loop runs once per two nodes of fast movement, so it runs floor(n / 2) times. Slow moves once per iteration, so it ends at the predecessor of the middle. You only need to recognise that the stopping point is the node before the middle, not the middle itself.
Worked example
Input: head = [10, 20, 30, 40, 50, 60, 70, 80, 90] Output: [10, 20, 30, 40, 60, 70, 80, 90] Explanation: The list has n = 9 nodes, so the middle node is at index 4, which holds 50. Removing it links 40 directly to 60, and every other node keeps its place.
Approach 1: Brute force: count, then walk
A beginner first counts the nodes, then walks the list again to the node before the middle. The first pass gives n. The second pass moves n // 2 - 1 steps from the head, which lands on the predecessor. Then the code unlinks the next node.
What's slow: the list is read twice, and the second pass only exists to find a position that the first pass already knew. The insight that fixes it is that a fast pointer can measure the half-way point while it moves, so the length is never needed.
Steps
- If
head.nextis null, return null, because a single node is its own middle. - Walk the whole list once and count the nodes into
n. - Set
prevto the head and move itn // 2 - 1steps forward. - Set
prev.nexttoprev.next.next, which removes the middle node. - Return the head.
Dry run
Use the example list 10, 20, 30, 40, 50, 60, 70, 80, 90. The head has a next node, so the list is longer than one node.
The counting pass visits all nine nodes, so n = 9. Then n // 2 - 1 = 3.
Move prev three steps: 10 to 20, then 20 to 30, then 30 to 40. Now prev is at 40.
Set 40.next to 60, which skips 50. The result is 10, 20, 30, 40, 60, 70, 80, 90.
Complexity
| Time | O(n) |
|---|---|
| Space | O(1) |
Let n be the number of nodes. The counting loop visits every node once, which costs n steps. The walk moves n // 2 - 1 steps, which is less than n, so the total is under 2n steps. Only the head, a counter and one pointer exist, so the extra space is constant.
PythonTested in our runner
from typing import List, Optional
class Solution:
def deleteMiddle(self, head: Optional[ListNode]) -> Optional[ListNode]:
# A single node is the middle, so the list becomes empty.
if head.next is None:
return None
# Pass 1: count the nodes.
n = 0
cur = head
while cur:
n += 1
cur = cur.next
# Pass 2: walk to the predecessor of index n // 2.
cur = head
for _ in range(n // 2 - 1):
cur = cur.next
cur.next = cur.next.next
return headThe Fixed Separation (Nth Node from End) infographic is part of Pro
A one-page visual of the pattern: when it applies, the steps and the invariant to keep.
Unlock the infographicSolution pattern
Fixed Separation (Nth Node from End)
Part of Two Pointers
Approach 2: One pass with slow and fast pointersOptimalFixed Separation (Nth Node from End)
What's slow: the brute force reads the whole list to learn n, then reads about half of it again to reach the predecessor. Both passes do work that the answer does not need.
The insight that fixes it: move a fast pointer two nodes per step and a slow pointer one node per step. When fast reaches the end, slow has covered half the distance. Start slow on a dummy node in front of the head, so it stops on the predecessor of the middle instead of on the middle itself.
Steps
- Create a dummy node whose
nextis the head. Setslowto the dummy andfastto the head. - While
fastandfast.nextare both not null, moveslowone node andfasttwo nodes. - When the loop stops,
slowis on the node before the middle. - Set
slow.nexttoslow.next.next, which unlinks the middle node. - Return
dummy.next, because the head may have been deleted.
Dry run
Use the example list 10, 20, 30, 40, 50, 60, 70, 80, 90. The dummy sits before 10, and slow starts there.
| Step | fast (index) | fast.next | slow after the move | Action |
|---|---|---|---|---|
| Start | 10 (0) | 20 | dummy (-1) | Enter the loop |
| 1 | 10 (0) | 20 | 10 (0) | fast moves to 30 (2) |
| 2 | 30 (2) | 40 | 20 (1) | fast moves to 50 (4) |
| 3 | 50 (4) | 60 | 30 (2) | fast moves to 70 (6) |
| 4 | 70 (6) | 80 | 40 (3) | fast moves to 90 (8) |
| 5 | 90 (8) | null | 40 (3) | Loop stops |
slow is at 40. Set 40.next to 60, which removes 50. Return dummy.next, which gives 10, 20, 30, 40, 60, 70, 80, 90.
Complexity
| Time | O(n) |
|---|---|
| Space | O(1) |
Let n be the number of nodes. Fast moves two nodes per iteration, so the loop runs at most n / 2 times, and each iteration does constant work. The final unlink is one constant-time step, so the total is O(n / 2 + 1), which is O(n). The dummy node and the two pointers are the only extra storage, so the space is O(1).
PythonTested in our runner
from typing import List, Optional
class Solution:
def deleteMiddle(self, head: Optional[ListNode]) -> Optional[ListNode]:
# The dummy node lets slow start before the head, so one code path covers every size.
dummy = ListNode(0, head)
slow = dummy
fast = head
# fast moves 2 per step and slow moves 1, so slow ends on the predecessor of the middle.
while fast and fast.next:
slow = slow.next
fast = fast.next.next
slow.next = slow.next.next
return dummy.nextCommon mistakes
- Starting
slowandfastboth athead. Thenslowlands on the middle node, and a singly linked list cannot unlink a node you are standing on. Startslowon the node before the middle, usually a dummy. - Checking only
fast.nextin the loop condition. After fast moves two steps it can be null, andfast.nextthen throws. Check thatfastis not null andfast.nextis not null. - Using
head.next.nextas the initial fast pointer without the one-node check. Whenn= 1,head.nextis null, so readinghead.next.nextcrashes. Guard the case or use a dummy node. - Returning
headafter deleting when the list has one node. The head is the deleted node, soheadstill points at the removed value. Returndummy.nextor null for that case. - Using
(n + 1) / 2as the index. It matches for evenn, but for n = 3 it gives index 2, which deletes the last node instead of index 1. Usen // 2, which is floor division. - Writing
for i in range(n // 2)in the brute force. That walks to the middle itself, and the code then cannot unlink it. Walkn // 2 - 1steps to reach the predecessor.
Edge cases
- A single node like [5]. The middle is the only node, so the result is an empty list, which means returning null.
- Two nodes like [1, 2]. The middle is index 1, so the result is [1]. This case checks that the predecessor is the head.
- Three nodes like [1, 2, 3]. The middle is index 1, so the result is [1, 3]. A version that removes the last node fails here.
- Four nodes like [1, 2, 3, 4]. The middle is index 2, so the result is [1, 2, 4]. Even lengths pick the right-hand middle.
- Duplicate values like [7, 7, 7]. Delete by position, so the result is [7, 7]. Comparing values would remove the wrong node.
- The maximum size of 10^5 nodes. The one-pass solution does about 5 * 10^4 loop iterations and uses O(1) space, so it runs well within limits.
Follow-ups interviewers ask
Follow-ups are part of Pro
The questions interviewers ask after you solve Delete the Middle Node of a Linked List, with how to answer them.
Unlock the follow-upsDelete the Middle Node of a Linked List FAQ
What is the time complexity of Delete the Middle Node of a Linked List?
The optimal solution runs in O(n) time, where n is the number of nodes. The fast pointer moves two nodes per loop, so the loop runs about n / 2 times. The brute force also runs in O(n) time, but it walks the list twice.
Why use two pointers for Delete the Middle Node of a Linked List?
The middle depends on the length, and the length is unknown until you count it. A fast pointer moving at twice the speed of a slow pointer reaches the end when slow is halfway. That gives the middle in one pass, without a count.
Can Delete the Middle Node of a Linked List be solved in O(1) extra space?
Yes. The one-pass solution uses a dummy node and two references, which does not grow with the list. The brute force also uses O(1) extra space. You do not need to copy the list into an array.
Why does the slow pointer start on a dummy node instead of the head?
Slow must stop one node before the middle so that it can change next. If the middle is the head, which happens only for one node, there is no node before it. A dummy node in front of the head always provides that node.
Why does the code return dummy.next and not head?
The head can be the deleted node when the list has one element. In that case the head still points to the removed value. The dummy's next always points to the first node that remains, or to null.
Asked at
See which companies ask this — Pro
Related problems
- Remove Nth Node From End of List · same technique: Fixed Separation (Nth Node from End)
- Middle of the Linked List · same technique: Fixed Separation (Nth Node from End)
- Trapping Rain Water · next harder, same pattern
- Sort Colors · same pattern: Two Pointers
- 3Sum · same pattern: Two Pointers
- Container With Most Water · same pattern: Two Pointers
- Longest Palindromic Substring · same pattern: Two Pointers
- Find the Duplicate Number · same pattern: Two Pointers
- Reverse Integer · same pattern: Two Pointers
- Two Sum II - Input Array Is Sorted · same pattern: Two Pointers