Условие

Дан односвязный список. Найдите средний узел списка. Если в списке чётное количество узлов, верните второй из двух средних узлов.

Примеры

Input: head = [1, 2, 3, 4, 5] Output: [3,4,5] Explanation: Средний узел — 3.

Input: head = [1, 2, 3, 4, 5, 6] Output: [4,5,6] Explanation: Средний узел — 4.

Решение

/**
 * Example:
 * var li = ListNode(5)
 * var v = li.`val`
 * Definition for singly-linked list.
 * class ListNode(var `val`: Int) {
 *     var next: ListNode? = null
 * }
 */
 fun middleNode(head: ListNode?): ListNode? {
    var slow = head // Медленный указатель
    var fast = head // Быстрый указатель

    // Быстрый указатель движется вдвое быстрее
    while (fast != null && fast.next != null) {
        slow = slow?.next
        fast = fast.next?.next
    }

    // Когда быстрый указатель достигает конца, медленный находится на середине
    return slow
}

Временная сложность

O(n), где n — длина списка, так как указатель проходит через каждый узел.

Пространственная сложность

O(1), не используются дополнительные структуры данных.