# Delete the Middle Node of a Linked List
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list)
Canonical: https://scaleengineer.com/dsa/problems/delete-the-middle-node-of-a-linked-list
**Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers)
**Data structures:** Linked List
---
## 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**, where `⌊x⌋` denotes the largest integer less than or equal to `x`.

* For `n` \= `1`, `2`, `3`, `4`, and `5`, the middle nodes are `0`, `1`, `1`, `2`, and `2`, respectively.

**Example 1:**

![](https://assets.glich.co/dsa/delete-the-middle-node-of-a-linked-list/image0.png) 

**Input:** head = [1,3,4,7,1,2,6]
**Output:** [1,3,4,1,2,6]
**Explanation:**
The above figure represents the given linked list. The indices of the nodes are written below.
Since n = 7, node 3 with value 7 is the middle node, which is marked in red.
We return the new list after removing this node. 

**Example 2:**

![](https://assets.glich.co/dsa/delete-the-middle-node-of-a-linked-list/image1.png) 

**Input:** head = [1,2,3,4]
**Output:** [1,2,4]
**Explanation:**
The above figure represents the given linked list.
For n = 4, node 2 with value 3 is the middle node, which is marked in red.

**Example 3:**

![](https://assets.glich.co/dsa/delete-the-middle-node-of-a-linked-list/image2.png) 

**Input:** head = [2,1]
**Output:** [2]
**Explanation:**
The above figure represents the given linked list.
For n = 2, node 1 with value 1 is the middle node, which is marked in red.
Node 0 with value 2 is the only node remaining after removing node 1.

**Constraints:**

* The number of nodes in the list is in the range `[1, 105]`.
* `1 <= Node.val <= 105`

# Approaches
## Two-Pass Traversal
A straightforward approach is to first determine the size of the linked list by traversing it completely. Once the size `n` is known, we can calculate the position of the middle node (`floor(n / 2)`). Then, we perform a second traversal to reach the node just before the middle node and update its `next` pointer to bypass and thus delete the middle node.
**Time:** O(N), where N is the number of nodes in the linked list. The first pass to count nodes takes O(N) time, and the second pass to find the predecessor takes up to O(N/2) time. The total complexity is O(N). · **Space:** O(1), as we only use a constant amount of extra space for pointers and a counter, regardless of the list size.
**Pros:** The logic is simple and directly follows from the problem definition.; It's easy to implement and debug.
**Cons:** Requires traversing the list twice (or one and a half times), which is less efficient than a single-pass solution in terms of the number of operations and potential cache performance.
### Explanation
This method breaks the problem down into two simpler sub-problems: finding the list's length and then finding a specific node by its index.

1.  **Count Nodes:** We start by iterating through the list from the `head` with a temporary pointer and a counter. The loop continues until the pointer becomes `null`, giving us the total count `n` of nodes.
2.  **Handle Edge Case:** If `n` is 1, the list becomes empty. The problem constraints state `n >= 1`, so we handle the `n=1` case by returning `null`.
3.  **Find Predecessor:** The middle node is at index `n / 2`. To delete it, we need its predecessor, which is at index `n / 2 - 1`. We start another traversal from the `head` and iterate `(n / 2) - 1` times. The node we land on is the predecessor of the middle node.
4.  **Delete Node:** Let the predecessor node be `prev`. The middle node is `prev.next`. We perform the deletion by setting `prev.next = prev.next.next`. This effectively removes the middle node from the list.

For example, in a list `[1,3,4,7,1,2,6]`, `n=7`. The middle index is `7/2 = 3`. The predecessor is at index `3-1=2`. We traverse to the node at index 2 (value 4), and set its `next` to point to the node at index 4 (value 1), skipping the node at index 3 (value 7).

```java
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode deleteMiddle(ListNode head) {
        if (head == null || head.next == null) {
            return null;
        }

        // First pass: count the number of nodes
        int n = 0;
        ListNode temp = head;
        while (temp != null) {
            n++;
            temp = temp.next;
        }

        // Calculate the index of the node to stop at (the one before the middle)
        int middleIndex = n / 2;

        // Second pass: find the node before the middle
        ListNode prev = head;
        // We need to traverse middleIndex - 1 steps from the head
        for (int i = 0; i < middleIndex - 1; i++) {
            prev = prev.next;
        }

        // Delete the middle node
        prev.next = prev.next.next;

        return head;
    }
}
```
### Algorithm
- Handle the edge case where the list has zero or one node. If `head` is `null` or `head.next` is `null`, the middle node is the head itself. Deleting it results in an empty list, so we return `null`.
- **First Pass:** Traverse the entire linked list to count the total number of nodes, `n`.
- Calculate the index of the middle node, which is `middleIndex = n / 2`.
- To delete the middle node, we need to find its predecessor. The predecessor is at `middleIndex - 1`.
- **Second Pass:** Initialize a pointer `prev` to `head`. Traverse the list `middleIndex - 1` times to move `prev` to the predecessor of the middle node.
- Once `prev` is at the correct position, update its `next` pointer to skip the middle node: `prev.next = prev.next.next`.
- Return the original `head` of the list.

## One-Pass using Fast and Slow Pointers
A more efficient approach is to use the classic fast and slow pointer technique. This allows us to find the middle of the list (or its predecessor) in a single pass, eliminating the need for a preliminary count of the nodes. By carefully initializing the pointers, we can make the `slow` pointer stop exactly at the node before the one we want to delete.
**Time:** O(N), where N is the number of nodes. The list is traversed only once. The `fast` pointer reaches the end in N/2 steps, making the approach linear. · **Space:** O(1), as we only use a constant amount of extra space for the two pointers.
**Pros:** Highly efficient, requiring only a single pass over the linked list.; Uses constant extra space.; It's an elegant solution and a common, useful pattern for solving linked list problems.
**Cons:** The pointer initialization and movement logic can be slightly less intuitive for beginners compared to the two-pass approach.
### Explanation
This optimized method uses two pointers, `slow` and `fast`, to traverse the list simultaneously but at different speeds. The `fast` pointer moves twice as fast as the `slow` pointer.

1.  **Edge Case:** First, we check if the list has only one node (`head.next == null`). If so, deleting the middle node leaves an empty list, so we return `null`.
2.  **Pointer Initialization:** We initialize `slow` to `head` and `fast` to `head.next.next`. This setup is crucial. When the `fast` pointer reaches the end, `slow` will naturally be at the predecessor of the middle node.
3.  **Traversal:** We iterate through the list with the condition `while (fast != null && fast.next != null)`. In each step, `slow` moves one node forward, and `fast` moves two nodes forward.
4.  **Finding the Predecessor:** Let's trace for a list of size 5 (`n=5`). The middle is at index 2. We need the predecessor at index 1.
    - Initial: `slow` at index 0, `fast` at index 2.
    - Iter 1: `slow` moves to index 1, `fast` moves to index 4.
    - Loop ends because `fast.next` is `null`. `slow` is at index 1, which is the correct predecessor.
5.  **Deletion:** Once the loop finishes, `slow` points to the node before the middle. We can then delete the middle node (`slow.next`) by setting `slow.next = slow.next.next`.

This approach is superior as it combines finding the correct position and performing the deletion into a single, efficient pass.

```java
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode deleteMiddle(ListNode head) {
        // Edge case: list with only one node.
        if (head.next == null) {
            return null;
        }

        // Initialize slow and fast pointers.
        // slow will point to the node before the middle.
        ListNode slow = head;
        ListNode fast = head.next.next;

        // Move fast pointer two steps and slow pointer one step.
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        // slow is now at the predecessor of the middle node.
        // Delete the middle node.
        slow.next = slow.next.next;

        return head;
    }
}
```
### Algorithm
- Handle the edge case: if the list has only one node (`head.next == null`), return `null`.
- Initialize a `slow` pointer to `head`.
- Initialize a `fast` pointer to `head.next.next`. This specific initialization is key to making `slow` land on the predecessor of the middle node.
- Loop while `fast != null` and `fast.next != null`:
  - Move `slow` one step forward: `slow = slow.next`.
  - Move `fast` two steps forward: `fast = fast.next.next`.
- After the loop terminates, the `fast` pointer has reached the end of the list, and the `slow` pointer is positioned at the node just before the middle node.
- Delete the middle node by updating the `next` pointer of the `slow` node: `slow.next = slow.next.next`.
- Return `head`.

# Solutions
### Java

```java
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public ListNode deleteMiddle ( ListNode head ) { ListNode dummy = new ListNode ( 0 , head ); ListNode slow = dummy , fast = head ; while ( fast != null && fast . next != null ) { slow = slow . next ; fast = fast . next . next ; } slow . next = slow . next . next ; return dummy . next ; } }
```

### CPP

```cpp
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: ListNode * deleteMiddle ( ListNode * head ) { ListNode * dummy = new ListNode ( 0 , head ); ListNode * slow = dummy ; ListNode * fast = head ; while ( fast && fast -> next ) { slow = slow -> next ; fast = fast -> next -> next ; } slow -> next = slow -> next -> next ; return dummy -> next ; } };
```

### Python

```python
# 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 ]: dummy = ListNode ( next = head ) slow , fast = dummy , head while fast and fast . next : slow = slow . next fast = fast . next . next slow . next = slow . next . next return dummy . next
```