Дан односвязный список. Верните его средний узел. Если узлов чётное число, средних два —
верните второй из них.
type ListNode struct {
Val int
Next *ListNode
}
// MiddleNode возвращает средний узел списка (для чётной длины — второй из двух средних).
func MiddleNode(head *ListNode) *ListNode
Примеры
1 → 2 → 3 → 4 → 5 → узел 3
1 → 2 → 3 → 4 → 5 → 6 → узел 4
1 → узел 1
nil → nil
Требования
- Вернуть сам узел исходного списка (указатель), а не копию. Список не изменять.
- Длина до 10⁶. Один проход, O(1) дополнительной памяти.
Устно: что поменять, чтобы для чётной длины возвращался первый из двух средних?
Где это нужно?
Разбор и эталонное решение — после своей попытки: на собеседовании подсказок не будет.
Сначала попробуй сам — подсказки не дают готовый ответ.