Хорошее еженедельное обновление мира Ruby on Rails: Зависть направляющих .
thestacktrace является хорошим общим подкастом программирования, который покрывает каждую вещь от мерзавца к Scala.
Чтобы использовать O (n) памяти и O (n) производительности, создайте стек; нажимайте все, когда выполняете итерацию в прямом направлении, затем выталкиваете все, что дает результат.
Чтобы использовать производительность O (n ^ 2) (но O (1) дополнительной памяти), прочитайте его каждый раз вперед, вверх узел перед последним, до которого вы дошли.
Пример:
IEnumerable<T> Reverse (Node head) {
Stack<Node> nodes = new Stack<Node>();
while(head != null) {
nodes.Push(head);
head = head.Next;
}
while(nodes.Count > 0) {
yield return nodes.Pop().Value;
}
}
Одним из отличительных признаков односвязного списка является то, что он , по сути, односвязные. Это улица с односторонним движением, и ее невозможно преодолеть, если вы не превратите ее во что-то еще (например, перевернутый односвязный список, стек, двусвязный список ...). Надо быть верным природе вещей.
Как было указано ранее; если вам нужно пройти по списку в обе стороны; вам нужен двусвязный список. Такова природа двусвязного списка, он действует в обоих направлениях.
На самом деле вам следует использовать двусвязный список.
Если это невозможно, я думаю, что лучшим вариантом будет создание копии списка, который был перевернут.
Другие варианты, такие как использование рекурсии (эффективное копирование списка в стек), могут привести к нехватке места в стеке, если список слишком длинный.
Если вам не хватает памяти, вы можете перевернуть список, перебрать его и снова отменить. В качестве альтернативы вы можете создать стек указателей на узлы (или что-то вроде указателя в C #).
Ну, наивным решением было бы отслеживать, на каком узле вы находитесь в данный момент, а затем выполнять итерацию с самого начала, пока вы не найдите этот узел, всегда сохраняя только что оставленный узел. Затем каждый раз, когда вы находите узел, на котором находитесь в данный момент, вы создаете узел, который только что покинули, сохраняете этот узел как тот, на котором находитесь сейчас, а затем повторяете его с самого начала.
Это, конечно, было бы ужасно плохая производительность.
I '
Ну, наивным решением было бы отслеживать, на каком узле вы сейчас находитесь, а затем выполнять итерацию с начало, пока вы не найдете этот узел, всегда сохраняя узел, который вы только что оставили. Затем каждый раз, когда вы находите узел, на котором находитесь в данный момент, вы создаете узел, который только что оставили, сохраняете этот узел как тот, на котором находитесь в данный момент, а затем повторяете итерацию с самого начала.
Это, конечно, было бы ужасно плохая производительность.
Я уверен, что у некоторых более умных людей есть лучшее решение.
Псевдокод (даже с ошибками):
current node = nothing
while current node is not first node
node = start
while node is not current node
previous node = node
node = next node
produce previous node
set current node to previous node
Предполагая, что ваш односвязный список реализует IEnumerable
var backwards = singlyLinkedList.Reverse();
Вам нужно будет добавить с помощью System.Linq;
в верхней части файла кода для использования методов расширения LINQ.
У меня возникла проблема с тем, чтобы мой браузер принял структуру данных, отправленную OP, но вот полностью рабочий пример, который я составил для своих собственных, аналогичных целей. Помимо функции, я также предоставляю структуру данных с именем / ветвями вместо заголовка / папки.
function to_ul (branch) {var ul = document.createElement ("ul"); для (var i = 0, n = branch.length; i
Наивный интервьюер может не осознавать, что есть лишние накладные расходы (в этом случае вы можете подумать, хотите ли вы там работать).
Это грязно, но работает:
class SinglyLinkedList {
SinglyLinkedList next;
int pos;
SinglyLinkedList(int pos) {
this.pos = pos;
}
SinglyLinkedList previous(SinglyLinkedList startNode) {
if (startNode == this) return null;
if (startNode.next == this) return startNode;
else return previous(startNode.next);
}
static int count = 0;
static SinglyLinkedList list;
static SinglyLinkedList head;
static SinglyLinkedList tail;
public static void main (String [] args) {
init();
System.out.println("Head: " + head.pos);
System.out.println("Tail: " + tail.pos);
list = head;
System.out.print("List forwards: ");
while (list != null) {
System.out.print(list.pos + ",");
list = list.next;
}
list = tail;
System.out.print("\nList backwards: ");
while (list.previous(head) != null) {
System.out.print(list.pos + ",");
list = list.previous(head);
}
}
static void init() {
list = new SinglyLinkedList(0);
head = list;
while (count < 100) {
list.next = new SinglyLinkedList(++count);
list = list.next;
}
tail = list;
}
}
Есть третье решение, на этот раз с использованием O (log (n))
памяти и O (n log (n))
времени, таким образом занимая золотую середину между двумя решениями в ответе Марка.
По сути, это обратный упорядоченный спуск двоичного дерева [ O (log (n))
], за исключением того, что на каждом шаге вы нужно найти вершину дерева [ O (n)
]:
Вот решение на Python (я не знаю C #):
def findMidpoint(head, tail):
pos, mid = head, head
while pos is not tail and pos.next is not tail:
pos, mid = pos.next.next, mid.next
return mid
def printReversed(head, tail=None):
if head is not tail:
mid = findMidpoint(head, tail)
printReversed(mid.next, tail)
print mid.value,
printReversed(head, mid)
Это можно было бы переделать, используя итерацию вместо рекурсии, но ценой ясности.
Например, для списка из миллиона записей три решения принимают следующий порядок:
Solution Memory Performance ========================================= Marc #1 4MB 1 million operations Mine 80B 20 million operations Marc #2 4B 1 trillion operations