Какая сложность у алгоритма разворота односвязного списка?

«Какая сложность у алгоритма разворота односвязного списка?» — вопрос из категории Алгоритмы и структуры данных, который задают на 24% собеседований PHP Разработчик. Ниже — развёрнутый ответ с разбором ключевых моментов.

Тип вопроса: Алгоритмы и структуры данных Вероятность: 24% Категория: PHP Разработчик

Ответ

Алгоритм итеративного разворота односвязного списка имеет временную сложность O(n) и пространственную сложность O(1).

O(n) по времени: Алгоритм проходит по списку ровно один раз, обрабатывая каждый узел.
O(1) по памяти (in-place): Не требуется дополнительных структур данных, пропорциональных размеру списка. Используется лишь несколько указателей.

Классическая итеративная реализация на PHP:

class SinglyListNode {
    public $value;
    public ?SinglyListNode $next = null;
    public function __construct($value) { $this->value = $value; }
}

function reverseList(?SinglyListNode $head): ?SinglyListNode {
    $prev = null;
    $current = $head;

    while ($current !== null) {
        // Сохраняем ссылку на следующий узел, прежде чем ее перезаписать.
        $nextNode = $current->next;
        // Разворачиваем указатель текущего узла назад.
        $current->next = $prev;
        // Сдвигаем указатели `prev` и `current` на один шаг вперед.
        $prev = $current;
        $current = $nextNode;
    }
    // `prev` теперь указывает на новую голову (старый хвост).
    return $prev;
}

// Пример использования:
$list = new SinglyListNode(1);
$list->next = new SinglyListNode(2);
$list->next->next = new SinglyListNode(3);
// Список: 1 -> 2 -> 3 -> null

$reversedList = reverseList($list);
// Теперь список: 3 -> 2 -> 1 -> null

Как это работает: Алгоритм последовательно "отрывает" каждый узел от старого списка и "прикрепляет" его к началу нового, формируя развернутую цепочку. Каждая из n итераций выполняет фиксированное количество операций, отсюда линейная сложность.