LeetCode 2095 - Delete the Middle Node of a Linked List

LeetCode Problem 2095

Difficulty: 🟡 Medium
Topics: Linked List, Two Pointers

Solution

Problem Understanding

The problem gives us the head of a singly linked list and asks us to delete the middle node. The definition of the middle node is based on 0-based indexing. If the list has n nodes, then the middle node is the node at index ⌊n / 2⌋.

For example:

If the list length is 1, the middle index is 0
If the list length is 4, the middle index is 2
If the list length is 7, the middle index is 3

After removing that node, we must return the head of the modified linked list.

A singly linked list only allows traversal in one direction, from head to tail. Since each node only knows about the next node, deleting a node requires access to the node immediately before it. This detail becomes important when designing the algorithm.

The constraints tell us that the linked list can contain up to 10^5 nodes. This means the solution must be efficient. An O(n) solution is ideal, while something significantly slower could become problematic for large inputs.

Several edge cases are important:

A list containing only one node. Deleting the middle node means the list becomes empty, so we return None.
A list containing two nodes. The middle index is 1, so the second node must be removed.
Even-length lists. The problem explicitly defines the middle as ⌊n / 2⌋, meaning the second of the two central nodes is removed.
Very large lists. The algorithm should avoid unnecessary extra memory or repeated traversals if possible.

Approaches

Brute Force Approach

A straightforward approach is to first count the total number of nodes in the linked list. Once we know the length n, we can compute the middle index as n // 2.

After finding the middle index, we traverse the list again until we reach the node immediately before the middle node. We then update its next pointer to skip the middle node.

This approach is correct because:

The first traversal accurately determines the list size.
The middle index formula matches the problem definition.
The second traversal locates the predecessor of the middle node so we can remove it safely.

Although this solution works efficiently enough for the constraints, it requires two passes through the list.

Optimal Approach

A better solution uses the fast and slow pointer technique.

The key insight is that if one pointer moves twice as fast as another, then when the fast pointer reaches the end of the list, the slow pointer will be positioned at the middle.

We maintain:

slow, which moves one step at a time
fast, which moves two steps at a time
prev, which tracks the node before slow

When traversal finishes:

slow points to the middle node
prev points to the node before the middle

We can then delete the middle node by setting:

prev.next = slow.next

This approach completes the task in a single traversal and uses constant extra space.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n)	O(1)	Two passes through the linked list
Optimal	O(n)	O(1)	Single traversal using fast and slow pointers

Algorithm Walkthrough

Handle the single-node edge case first.

If head.next is None, then the list contains only one node. Deleting the middle node leaves an empty list, so return None. 2. Initialize three pointers.

Set:

slow = head
fast = head
prev = None

The slow pointer will eventually reach the middle node. The fast pointer moves twice as quickly. The prev pointer tracks the node immediately before slow. 3. Traverse the linked list.

Continue while both fast and fast.next exist:

Move prev to slow
Move slow one step forward
Move fast two steps forward

Identify the middle node.

When the loop ends:

slow points to the middle node
prev points to the node before the middle

Delete the middle node.

Update:

prev.next = slow.next

This removes the middle node from the linked list. 6. Return the modified list head.

Since the head itself is unchanged except in the single-node case, return head.

Why it works

The fast pointer advances two nodes for every one node advanced by the slow pointer. Therefore, when the fast pointer reaches the end of the list, the slow pointer has traveled exactly half the distance, placing it at the middle node. Since prev always trails one step behind slow, it provides direct access to the node needed to reconnect the list after deletion.

Python Solution

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution:
    def deleteMiddle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        # If there is only one node, deleting the middle leaves an empty list
        if head.next is None:
            return None

        slow = head
        fast = head
        prev = None

        # Find the middle node
        while fast and fast.next:
            prev = slow
            slow = slow.next
            fast = fast.next.next

        # Remove the middle node
        prev.next = slow.next

        return head

The implementation begins by handling the special case where the list contains only one node. Since that node is also the middle node, the correct result is an empty list.

Next, the algorithm initializes the slow, fast, and prev pointers. During traversal, slow advances one node at a time while fast advances two nodes at a time. This guarantees that slow reaches the middle when the loop finishes.

The prev pointer is updated before moving slow, ensuring that it always points to the node immediately before the middle node. Once the middle node is identified, the algorithm removes it by reconnecting prev.next to the node after slow.

Finally, the modified head is returned.

Go Solution

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func deleteMiddle(head *ListNode) *ListNode {
    // Single node case
    if head.Next == nil {
        return nil
    }

    slow := head
    fast := head
    var prev *ListNode = nil

    // Find the middle node
    for fast != nil && fast.Next != nil {
        prev = slow
        slow = slow.Next
        fast = fast.Next.Next
    }

    // Delete the middle node
    prev.Next = slow.Next

    return head
}

The Go implementation follows the same logic as the Python version. The primary difference is explicit pointer handling with *ListNode.

Go uses nil instead of Python's None. The traversal loop checks both fast != nil and fast.Next != nil before advancing the pointers to avoid dereferencing a nil pointer.

Because linked lists in Go are already reference-based structures, modifying prev.Next directly updates the original list.

Worked Examples

Example 1

Input:

[1,3,4,7,1,2,6]

Initial state:

Step	prev	slow	fast
Start	None	1	1

Iteration 1:

prev = 1
slow = 3
fast = 4

Step	prev	slow	fast
1	1	3	4

Iteration 2:

prev = 3
slow = 4
fast = 1

Step	prev	slow	fast
2	3	4	1

Iteration 3:

prev = 4
slow = 7
fast = 6

Step	prev	slow	fast
3	4	7	6

Loop ends because fast.next is None.

Middle node is 7.

Delete it:

4 -> 1

Final list:

[1,3,4,1,2,6]

Example 2

Input:

[1,2,3,4]

Initial state:

Step	prev	slow	fast
Start	None	1	1

Iteration 1:

prev = 1
slow = 2
fast = 3

Step	prev	slow	fast
1	1	2	3

Iteration 2:

prev = 2
slow = 3
fast = None

Step	prev	slow	fast
2	2	3	None

Middle node is 3.

Delete it:

2 -> 4

Final list:

[1,2,4]

Example 3

Input:

[2,1]

Initial state:

Step	prev	slow	fast
Start	None	2	2

Iteration 1:

prev = 2
slow = 1
fast = None

Step	prev	slow	fast
1	2	1	None

Middle node is 1.

Delete it:

2 -> None

Final list:

[2]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each node is visited at most once
Space	O(1)	Only a few pointer variables are used

The fast and slow pointer technique allows the algorithm to locate the middle node in a single traversal. No auxiliary data structures are needed, so the extra memory usage remains constant regardless of input size.

Test Cases

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def deleteMiddle(self, head):
        if head.next is None:
            return None

        slow = head
        fast = head
        prev = None

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

        prev.next = slow.next

        return head

def build_list(values):
    dummy = ListNode()
    current = dummy

    for value in values:
        current.next = ListNode(value)
        current = current.next

    return dummy.next

def to_list(head):
    result = []

    while head:
        result.append(head.val)
        head = head.next

    return result

sol = Solution()

# Example 1
head = build_list([1, 3, 4, 7, 1, 2, 6])
assert to_list(sol.deleteMiddle(head)) == [1, 3, 4, 1, 2, 6]  # odd length list

# Example 2
head = build_list([1, 2, 3, 4])
assert to_list(sol.deleteMiddle(head)) == [1, 2, 4]  # even length list

# Example 3
head = build_list([2, 1])
assert to_list(sol.deleteMiddle(head)) == [2]  # two-node list

# Single node case
head = build_list([10])
assert sol.deleteMiddle(head) is None  # list becomes empty

# Three nodes
head = build_list([5, 6, 7])
assert to_list(sol.deleteMiddle(head)) == [5, 7]  # remove center node

# Five nodes
head = build_list([1, 2, 3, 4, 5])
assert to_list(sol.deleteMiddle(head)) == [1, 2, 4, 5]  # remove index 2

# Duplicate values
head = build_list([1, 1, 1, 1])
assert to_list(sol.deleteMiddle(head)) == [1, 1, 1]  # ensure correct position removed

# Larger list
head = build_list(list(range(10)))
assert to_list(sol.deleteMiddle(head)) == [0, 1, 2, 3, 4, 6, 7, 8, 9]  # remove index 5

Test	Why
`[1,3,4,7,1,2,6]`	Validates odd-length behavior
`[1,2,3,4]`	Validates even-length behavior
`[2,1]`	Ensures two-node handling works
`[10]`	Tests single-node edge case
`[5,6,7]`	Confirms correct middle deletion in small odd list
`[1,2,3,4,5]`	Verifies floor division middle index
`[1,1,1,1]`	Ensures deletion is position-based, not value-based
`range(10)`	Tests larger even-length input

Edge Cases

A single-node linked list is the most important edge case. In this scenario, the only node is also the middle node. A common bug is attempting to access prev.next when prev is still None. The implementation avoids this by explicitly checking whether head.next is None before starting traversal and immediately returning None.

A two-node linked list is another subtle case. Since the middle index is 1, the second node must be deleted. Some incorrect implementations accidentally remove the first node because they mis-handle even-length lists. The fast and slow pointer approach naturally places slow on the second node, ensuring the correct deletion.

Even-length linked lists can also cause off-by-one errors. The problem defines the middle as ⌊n / 2⌋, meaning the second middle node should be removed. The traversal logic guarantees this behavior because the slow pointer advances after every fast pointer movement, causing it to settle on the correct middle position for both odd and even list lengths.