657. Delete the Middle Node of a Linked List
You receive head, the first node of a singly linked list with n nodes. The middle node is the one at position ⌊n / 2⌋, counting from 0 — so for lists of length 1, 2, 3, 4, 5 the middle is the node at index 0, 1, 1, 2, 2 respectively.
Write a function that unlinks the middle node and returns the head of the resulting list. If the list has a single node, deleting it leaves an empty list — return null (None).
Example 1:
Input: head = [2, 4, 6, 8, 10]
Output: [2, 4, 8, 10]
Explanation: n = 5, so the middle is index ⌊5/2⌋ = 2 — the node holding 6. Unlinking it splices 4 directly to 8.
Example 2:
Input: head = [5, 9]
Output: [5]
Explanation: n = 2, so the middle is index ⌊2/2⌋ = 1 — the second node. Only the head remains.
Constraints:
- 1 ≤ n ≤ 10⁵ (number of nodes)
- 1 ≤ Node.val ≤ 10⁵
- The middle node is the one at 0-based index ⌊n / 2⌋
Hints:
You can't index a linked list — but you can count. One pass to find n, a second pass to stop at node ⌊n/2⌋ − 1 and splice around its successor.
One pass is enough with two pointers: advance fast two steps for every one step of slow. When fast runs off the end, slow stands on the middle node.
To delete slow you need the node *before* it — carry a prev pointer (or start fast ahead) so the splice prev.next = slow.next is O(1).
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: head = [2, 4, 6, 8, 10]
Expected output: [2, 4, 8, 10]