316. Delete Middle Node of Linked List

Given the head of a singly linked list, delete the middle node and return the head.

The middle node is at index ⌊n/2⌋ (0-indexed). For [1,3,4,7,1,2,6] (n=7), delete index 3 (value=7).

Use slow/fast pointers to find the middle in one pass.

Input: Head of a singly linked list.

Output: Head of the list with middle node removed.

Examples

Example 1

Input: [1,3,4,7,1,2,6]
Output: [1,3,4,1,2,6]
Explanation: n=7, middle index=3 (value=7). Remove it. Result: [1,3,4,1,2,6].

Example 2

Input: [2,1]
Output: [2]
Explanation: n=2, middle index=1 (value=1). Remove node(1). Result: [2].

Example 3

Input: [1]
Output: []
Explanation: Single node is the middle. Remove it. Return NULL.