Распечатать односвязный список задом наперед, в постоянном пространстве и линейном времени

Question

Я слышал вопрос на собеседовании:

"Напечатать односвязный список задом наперед, в постоянном пространстве и линейном времени. "

Мое решение состояло в том, чтобы перевернуть связанный список на месте и затем напечатать его вот так. Есть ли другое решение, которое не является разрушительным?

Answer 1

Вы уже выяснили большую часть ответа: переверните связанный список на месте и просмотрите список обратно в начало, чтобы распечатать его.Чтобы он не был (навсегда) разрушительным, переверните связанный список на место снова , пока вы перемещаетесь назад к началу и печатаете его.работает, если у вас либо только один поток выполнения, либо весь обход обходится критическим разделом, так что только один поток делает это за один раз (т. е. второй поток не может играть со списком в середине обхода).1005 *

Answer 2

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

Answer 3

Просто итерируйте и печатайте по пути, но переверните монитор вверх ногами.

˙uoıʇɐɯɹoɟsuɐɹʇ ʇxǝʇ ǝlʇʇıl ɐ ʍıʍ ʇɥƃıɹ ʇsoɯlɐ ʞool uɐɔ ʇI

Answer 4

Хорошо, это может быть вопрос для интервью, но на самом деле это вопрос, стоящий за книгой по алгоритмам weis.В вопросе четко говорится, что мы не можем использовать рекурсию (то, что интервьюер будет скрывать и раскрывать позже), поскольку рекурсия не будет использовать постоянное пространство, рекурсия Мослоты станет основной точкой обсуждения в будущем.Решение обратной печати и обратного возврата.

Answer 5

Вот нетрадиционный подход: измените консоль на порядок чтения справа налево, а затем распечатайте список в обычном порядке.Они появятся в обратном порядке.Необходимость посещения фактических данных в обратном порядке не является ограничением для проблемы.

Answer 6

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

Таким образом, каждый узел в списке будет проходить вниз, пока последний не сможет и не перейдет прямо к записи, затемкаждый из резервных копий цепочки будет записывать после последнего весь путь обратно вперед.

Редактировать

Это на самом деле не соответствует спецификациям из-залинейное пространство в стеке.Если у вас есть что-то снаружи для обхода функций и метода записи в начало строки, базовая логика все же может работать.