Обратный порядок узлов односвязного списка

Условие

Дан односвязный список, каждый его элемент содержит два поля:

• value — значение узла;
• next — ссылку на следующий узел. Необходимо реализовать алгоритм, который перестраивает связи списка в обратном направлении, т.е. первый элемент становится последним, а последний — первым.

class node{
    public $next;
    public $value;
    
}

A->B->C->...->N

Ответ

Переворачивайте next каждого узла, предварительно сохраняя старого преемника. После прохода указатель previous становится новой головой списка.

function reverseList(?node $head): ?node {
    $previous = null;
    $current = $head;
    while ($current !== null) {
        $next = $current->next;
        $current->next = $previous;
        $previous = $current;
        $current = $next;
    }
    return $previous;
}

Время O(n), дополнительная память O(1). Пустой список возвращает null, одиночный остаётся тем же узлом. Предполагается отсутствие цикла; функция меняет исходные связи, а не создаёт копию.