Алгоритм Вопрос .. Связанный список

Question

Сценарий выглядит следующим образом: -

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

Ну,Алгоритм должен занимать линейное время.

Решение, которое я подумал об использовании другой структуры данных A Stack .. С помощью которой односвязный список можно было бы легко перевернуть, со всеми указателями, указывающими назад .. Но ясомневаюсь, что следующая реализация приведет к линейной сложности времени .. Пожалуйста, прокомментируйте это .. И если какой-либо другой эффективный алгоритм существует, тогда, пожалуйста, обсудите ..

Спасибо.

Answer 1

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

node* reverse(node *in) {
   out = NULL;
   while (in) {
      node = in;
      in = in->next;
      node->next = out;
      out = node;
   }
   return out;
}

Answer 2

2 раза O (N) = O (2 * n) по-прежнему равно O (N). Поэтому сначала нажмите N элементов, а затем извлеките N элементов из стека, и это действительно линейно по времени, как вы и ожидали.

См. Также раздел Умножение на константу в записи википедии "Big O Notation".

Answer 3

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

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

Answer 4

В предыдущих ответах уже упоминалось (и справедливо), что решение, использующее манипуляции с указателями, и решение, использующее стек: O(n).

Остается вопрос о сравнении производительности в реальном времени (сложности машинного цикла) двух разных реализаций функции reverse().

Я ожидаю, что следующие два аспекта могут иметь значение:

1. Реализация стека. Является ли требуется максимальная глубина стека для быть явно указан? Если да, то как это указано? Если нет, то как стек управляет памятью как размер растет сколь угодно большим?

2. Я думаю, что узлы должны быть скопированы из списка в стек. [Есть ли способ без копирования?] В этом случае Скопировать сложность узла необходимо быть учтены. Это потому что размер узла может быть (произвольно) большой.

Учитывая это, изменение места путем манипулирования указателями кажется мне более привлекательным.

Answer 5

Вы можете использовать стек для реализации O (n). Но рекурсивное решение использует стек (THE stack)! И, как и все рекурсивные алгоритмы, это эквивалентно циклу. Однако в этом случае использование рекурсии или явного стека создаст сложность пространства O (n), которая совершенно не нужна.

Answer 6

Для списка размером n вы звоните n раз push и n раз pop, оба из которых являются O(1) операциями, поэтому вся операция равна O(n).