Delete the Middle Node of a Linked List

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⌋<sup>th</sup> 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: Input: head = [1,3,4,7,1,2,6] Output: [1,3,4,1,2,6] Explanation: 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: 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: 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<sup>5</sup>]. 1 <= Node.val <= 10<sup>5</sup>

## Delete the Middle Node of a Linked List

This problem asks us to delete the middle node of a given linked list. The middle node is defined as the floor(n/2)-th node, where n is the number of nodes in the list, and the indexing is 0-based.

### Naive Approach

1.  **Calculate the length of the linked list:** Traverse the linked list once to determine the number of nodes, `n`. O(N) time complexity.
2.  **Find the middle node:** Calculate the index of the middle node as `middle = n // 2`.
3.  **Traverse to the node before the middle node:** Start from the head and traverse to the node at index `middle - 1`. O(N) time complexity.
4.  **Delete the middle node:** Update the `next` pointer of the node before the middle node to skip the middle node.

This approach has a time complexity of O(N) because we traverse the linked list twice.

### Optimal Approach: Tortoise and Hare (Fast and Slow Pointers)

We can use the tortoise and hare approach (also known as the fast and slow pointers approach) to find the middle node in a single traversal.

1.  **Initialize slow and fast pointers:** Start both `slow` and `fast` pointers at the head of the linked list.
2.  **Traverse the linked list:** Move the `fast` pointer two steps at a time and the `slow` pointer one step at a time.
3.  **Find the node before the middle node:** When the `fast` pointer reaches the end of the list, the `slow` pointer will be at the node before the middle node.
4.  **Delete the middle node:** Update the `next` pointer of the node before the middle node to skip the middle node.

Here's an example to illustrate the process:

Suppose the linked list is `1 -> 2 -> 3 -> 4 -> 5`.

1.  `slow = head`, `fast = head`
2.  `slow = 2`, `fast = 3`
3.  `slow = 3`, `fast = 5`
4.  `fast` reaches the end of the list. `slow` is at node `3`, which is the node before the middle node `4`.
5.  Update `slow.next = slow.next.next` to delete the middle node.

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

def delete_middle(head: ListNode) -> ListNode:
    """Deletes the middle node of a linked list.
    """
    if not head or not head.next:
        return None  # Handle empty or single-node list

    slow, fast = head, head
    prev = None # Track the node before slow

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

    # Now slow points to the middle node.
    # prev points to the node BEFORE the middle node.
    prev.next = slow.next  # skip over the middle node

    return head

Big(O) Time Complexity Analysis

The optimal solution has a time complexity of O(N), where N is the number of nodes in the linked list. This is because we traverse the linked list once using the slow and fast pointers.

Big(O) Space Usage Analysis

The optimal solution has a space complexity of O(1) because we only use a few constant extra variables (slow, fast, prev) regardless of the size of the linked list. Thus the space usage is constant.

Edge Cases

1. Empty list: If the list is empty (head is None), there is no middle node to delete. We should return None.
2. Single-node list: If the list has only one node, deleting the middle node (which is the only node) would result in an empty list. We should return None.
3. Two-node list: If the list has two nodes, the middle node is the second node. After deleting the middle node, the list becomes a single-node list. This is handled correctly by the algorithm.
4. List with even number of nodes: Consider the list 1 -> 2 -> 3 -> 4. The middle node is 3. slow ends up pointing to 2, and then we set slow.next = slow.next.next, so 2.next = 4. Thus, the resulting list is 1 -> 2 -> 4.
5. List with odd number of nodes: Consider the list 1 -> 2 -> 3 -> 4 -> 5. The middle node is 3. slow ends up pointing to 2, and then we set slow.next = slow.next.next, so 2.next = 4. Thus, the resulting list is 1 -> 2 -> 4 -> 5.