Reverse Linked List

Условие

Разверните односвязный список.

Примеры

Input: head = [1, 2, 3, 4, 5]

Output: [5, 4, 3, 2, 1]

Input: head = [1, 2]

Output: [2, 1]

Input: head = []

Output: []

Решение

// Определение структуры узла связанного списка
class ListNode(var value: Int) {
    var next: ListNode? = null
}

/**
 * Пример:
 * var li = ListNode(5)
 * var v = li.value
 * 
 * Пример создания односвязного списка (1 -> 2 -> 3 -> 4 -> 5 -> null):
 * val head = ListNode(1)
 * head.next = ListNode(2)
 * head.next?.next = ListNode(3)
 * head.next?.next?.next = ListNode(4)
 * head.next?.next?.next?.next = ListNode(5)
 */
fun reverseList(head: ListNode?): ListNode? {
		// Храним предыдущий элемент.
		var prev: ListNode? = null
		// Храним текущий эелемент (начиная с head списка).
    var current = head
    
    // Итерируемся по списку
    while (current != null) {
        val nextNode = current.next  // Сохраняем ссылку на следующий узел.
        current.next = prev          // Текущий узел перенаправляется на предыдущий.
        prev = current
        current = nextNode
    }
    
    return prev  // Возвращаем новый head списка
}

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

O(n), где n — количество узлов в списке. Это связано с тем, что алгоритм проходит по каждому узлу ровно один раз, выполняя при этом фиксированное количество операций для каждого узла (сохранение ссылки на следующий узел, изменение ссылки на предыдущий узел, и перемещение указателей).

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

O(1). Алгоритм использует только фиксированное количество дополнительных переменных (prev, current, nextNode), независимо от размера входного списка. Поэтому потребление дополнительной памяти не зависит от размера списка и остается постоянным.