Различные реализации обратного связанного списка

Question

Различные реализации обратного связанного списка

Я нашел несколько реализаций обратного связанного списка в php, и большинство из них одинаковы с некоторыми небольшими отличиями, как это:

public function reverse() {
if ( $this->_firstNode !== NULL ) {
if ( $this->_firstNode->next !== NULL ) {
$reversed = $temp = NULL;
$current = $this->_firstNode;
while ( $current !== NULL ) {
$temp = $current->next;
$current->next = $reversed;
$reversed = $current;
$current = $temp;
}
$this->_firstNode = $reversed;
}
}
}

Но я думаю, что это можно изменить на это:

public function reverse() {
while ( $this->_firstNode->next !== NULL ) {
$oldFirstNode = $this->_firstNode;
$this->_firstNode = $oldFirstNode->next;
$oldFirstNode->next = NULL;
$this->_firstNode->next = $oldFirstNode;
}
}

Я прав?

1

data-structures linked-list php

Решение

Другие решения

Других решений пока нет …

Источник

Accepted Answer

Ваш код не работает по двум причинам:

Вы не проверяете пустой список. Способ не учитывает случай, в котором $this->_firstNode является NULL,
Метод не работает, если список содержит только один элемент.
Если список содержит два или более элементов, метод инвертирует только первые два элемента списка, затем он попадает в бесконечный цикл. Это потому что в последней строке тела пока вы обновляете $this->_firstNode->next со значением $oldFirstNodeи в следующей итерации вы проверяете $this->_firstNode->next !== NULL, который отличается от NULL так как это значение $oldFirstNodeи функция продолжит цикл на этих двух узлах.

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

В заключение отметим, что если алгоритм всегда используется для определенной базовой задачи, очень трудно найти новый, более эффективный алгоритм.

1