Problem statement

You are given the head of a singly linked list with n nodes. Remove its middle node and return the head of the modified list.

Counting positions from 0, the middle node of a list of n nodes is the one at index ⌊n / 2⌋: for n = 1, 2, 3, 4, 5 that is index 0, 1, 1, 2, 2. A one-node list therefore becomes empty.

Example 1

Input: head = [4,8,15,16,23,42]
Output: [4,8,15,23,42]
Explanation: n = 6, so the middle is index 3 — the node holding 16.

Example 2

Input: head = [7,2]
Output: [7]
Explanation: n = 2, so index 1 (the node holding 2) is removed.

Example 3

Input: head = [9]
Output: []
Explanation: The only node is the middle one; nothing is left.

Constraints

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

Hints for Delete the Middle Node of a Linked List

1. Hint 1

   To unlink a node you need the node before it, so aim to stop one step short of the middle.

2. Hint 2

   A slow pointer that moves one step while a fast pointer moves two reaches the middle when the fast one runs out — no need to count first.

3. Hint 3

   Give the fast pointer a two-node head start (fast = head.next.next) and the slow pointer stops exactly at the node before index ⌊n / 2⌋. Handle n = 1 separately.

How to solve Delete the Middle Node of a Linked List

Use the slow/fast pointer race, but start the fast pointer two nodes ahead so the slow pointer finishes on the node before the middle, which is the one whose link must change.

Approach

1. If the list has one node, return an empty list.
2. Set slow = head and fast = head.next.next.
3. While fast and fast.next both exist, move slow one step and fast two steps.
4. Unlink the middle: slow.next = slow.next.next. Return head.

Why it works

After k loop iterations slow is at index k and fast at index 2k + 2. The loop stops at the first k with 2k + 2 >= n - 1, which makes k = ⌊n / 2⌋ - 1 — the predecessor of the middle — for both even and odd n.

Complexity

• Time — O(n)
• Space — O(1)

Pitfalls

• With an even length the middle is the second of the two central nodes (index n / 2).
• Starting both pointers at the head leaves slow on the middle itself, which cannot be unlinked in a singly linked list without its predecessor.
• A one-node list has no predecessor at all — return the empty list.

Reference solution

Python

from typing import Optional

def deleteMiddle(head: Optional[ListNode]) -> Optional[ListNode]:
    if head.next is None:
        return None
    slow, fast = head, head.next.next
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    slow.next = slow.next.next
    return head

Java

public static ListNode deleteMiddle(ListNode head) {
    if (head.next == null) return null;
    ListNode slow = head, fast = head.next.next;
    while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; }
    slow.next = slow.next.next;
    return head;
}

C++

ListNode* deleteMiddle(ListNode* head) {
    if (!head->next) return nullptr;
    ListNode *slow = head, *fast = head->next->next;
    while (fast && fast->next) { slow = slow->next; fast = fast->next->next; }
    slow->next = slow->next->next;
    return head;
}

JavaScript

var deleteMiddle = function(head) {
    if (head.next === null) return null;
    var slow = head, fast = head.next.next;
    while (fast !== null && fast.next !== null) { slow = slow.next; fast = fast.next.next; }
    slow.next = slow.next.next;
    return head;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More two pointers problems

• Merge Two Sorted Linked Lists in Reverse Order Medium
• Rotate a Linked List Medium
• Segregate Even and Odd Nodes in a Linked List Medium
• Maximum Twin Sum of a Linked List Medium
• Swapping Nodes in a Linked List Medium
• Merge In Between Linked Lists Medium