Delete the Middle Node of a Linked List

medium linked list two pointers

Problem

Given the head of a singly linked list, delete the middle node and return the new head. The middle node of a list of length n is at position ⌊n/2⌋ (0-indexed). Use slow and fast pointers — fast moves twice as quickly, so when fast hits the end, slow sits at the middle.

Inputhead = 5 → 8 → 1 → 3 → 9 → null

Output5 → 8 → 3 → 9 → null

Length 5; middle index 2 (value 1) is removed.

node values (comma-separated)

def delete_middle(head):
    if head is None or head.next is None:
        return None
    slow, fast, prev = head, head, None
    while fast and fast.next:
        prev = slow
        slow = slow.next
        fast = fast.next.next
    prev.next = slow.next
    return head

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

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

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

Explanation

To delete the middle node, you first have to find the middle. The neat trick is the slow and fast pointer technique, which locates the middle in a single pass without ever counting the list's length first.

Start slow and fast both at the head. Each loop step moves slow forward one node and fast forward two nodes. Since fast travels twice as fast, by the time it reaches the end, slow has only made it halfway — right to the middle.

We also keep a prev pointer trailing one step behind slow. That matters because to remove the middle node we need the node just before it, so we can do prev.next = slow.next to splice it out.

Example: 5 → 8 → 1 → 3 → 9 (length 5, middle index 2 is 1). The pointers advance until slow lands on 1 with prev on 8. We set 8.next = 3, giving 5 → 8 → 3 → 9.

The early check if head is None or head.next is None handles a list of zero or one node by returning None, since removing the only node leaves an empty list. It runs in one linear pass with no extra memory.

Time: O(n) Space: O(1)