Существует большое рекурсивное решение этой проблемы, основанное на следующих наблюдениях:
- Обратной стороной пустого списка является пустой список.
- Оборотная сторона одиночного списка сама по себе.
- Обратный список узла N, за которым следует список L, является обратным списку L, за которым следует узел N.
Таким образом, вы можете реализовать функцию реверса, используя псевдокод по следующим направлениям:
void reverseList(Node node) {
if (node == null) return; // Reverse of empty list is itself.
if (node.next == null) return; // Reverse of singleton list is itself.
reverseList(node.next); // Reverse the rest of the list
appendNodeToList(node, node.next); // Append the new value.
}
Наивная реализация этого алгоритма выполняется в O (n 2 ), так как для каждого обращения требуется добавление, которое требует сканирования O (n) поверх остальной части списка. Тем не менее, вы можете реально заставить это работать в O (n), используя умное наблюдение. Предположим, что у вас есть связанный список, который выглядит следующим образом:
n1 --> n2 --> [rest of the list]
Если вы перевернете список, начинающийся с n2, то вы получите следующую настройку:
n1 [reverse of rest of the list] --> n2
| ^
+------------------------------------------+
Таким образом, вы можете добавить n1 к обратной стороне остального списка, установив n1.next.next = n1, который изменит n2, новый конец обратного списка, на n1:
[reverse of the rest of the list] --> n2 --> n1
А ты золотой! Еще раз псевдокод:
void reverseList(Node node) {
if (node == null) return; // Reverse of empty list is itself.
if (node.next == null) return; // Reverse of singleton list is itself.
reverseList(node.next); // Reverse the rest of the list
node.next.next = node; // Append the new value.
}
РЕДАКТИРОВАТЬ: Как указал Ран, он использует стек вызовов для своего пространства хранения и, следовательно, риск переполнения стека. Если вы хотите использовать явный стек вместо этого, вы можете сделать это так:
void reverseList(Node node) {
/* Make a stack of the reverse of the nodes. */
Stack<Node> s = new Stack<Node>();
for (Node curr = node; node != null; node = node.next)
s.push(curr);
/* Start unwinding it. */
Node curr = null;
while (!s.empty()) {
Node top = s.pop();
/* If there is no node in the list yet, set it to the current node. */
if (curr == null)
curr = top;
/* Otherwise, have the current node point to this next node. */
else
curr.next = top;
/* Update the current pointer to be this new node. */
curr = top;
}
}
Я считаю, что это аналогично инвертирует элементы связанного списка.