Formatted question description: https://leetcode.ca/all/2095.html

# 2095. Delete the Middle Node of a Linked List (Medium)

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⌋`

node from the ^{th}**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:**

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:**

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:**

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, 10`

.^{5}] `1 <= Node.val <= 10`

^{5}

**Similar Questions**:

- Remove Nth Node From End of List (Medium)
- Reorder List (Medium)
- Remove Linked List Elements (Easy)
- Middle of the Linked List (Easy)

## Solution 1.

```
// OJ: https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/
// Time: O(N)
// Space: O(1)
class Solution {
int getLength(ListNode *head) {
int ans = 0;
for (; head; ++ans, head = head->next);
return ans;
}
public:
ListNode* deleteMiddle(ListNode* head) {
ListNode dummy, *p = &dummy;
dummy.next = head;
int len = getLength(head) / 2;
for (int i = 0; i < len; ++i, p = p->next);
p->next = p->next->next;
return dummy.next;
}
};
```

## Solution 2. Fast-Slow Pointers

```
// OJ: https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/
// Time: O(N)
// Space: O(1)
class Solution {
public:
ListNode* deleteMiddle(ListNode* head) {
ListNode dummy, *fast = &dummy, *slow = &dummy;
dummy.next = head;
while (fast->next && fast->next->next) {
slow = slow->next;
fast = fast->next->next;
}
slow->next = slow->next->next;
return dummy.next;
}
};
```