Как прочитать односвязный список задом наперед?
https://stackoverflow.com/questions/1116720
-
12-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Один из методов, который я могу придумать, — это перевернуть список, а затем прочитать его.Но это предполагает изменение списка, а это плохо.
ИЛИ я могу сделать копию списка, а затем отменить его, но для этого потребуется дополнительная память O(n).Есть ли лучший метод, который не использует дополнительную память, не изменяет список и работает за время O (n)
Код обратного связанного списка выглядит примерно так в С#
Void Reverse (Node head)
{
Node prev= null;
Node current = head;
Node nextNode = null;
while (current!=null)
{
nextNode = current.Next;
current.Next = prev;
prev=current;
current = nextNode;
}
head = prev;
}
Рекурсивное решение
void ReadBackWard (Node n)
{
if (n==null)
return;
else
ReadBackward(n.Next);
Console.WriteLine(n.Data);
}
Решение
Чтобы использовать память 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#).
void reverse_print(node *head)
{
node *newHead = NULL, *cur = head;
if(!head) return;
// Reverse the link list O(n) time O(1) space
while(cur){
head = head->next;
cur->next = newHead;
newHead = cur;
cur = head;
}
// Print the list O(n) time O(1) space
cur = newHead;
while(cur) {
printf(" %d", cur->val);
cur = cur->next;
}
// Reverse the link list again O(n) time O(1) space
cur = newHead;
while(cur){
newHead = newHead->next;
cur->next = head;
head = cur;
cur = newHead;
}
// Total complexity O(n) time O(1) space
}
Существует третье решение, на этот раз с использованием 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
Предполагая, что ваш односвязный список реализует IEnumerable<T>, вы можете использовать метод обратного расширения LINQ:
var backwards = singlyLinkedList.Reverse();
Вам нужно будет добавить using System.Linq; директиву в верхней части файла кода, чтобы использовать методы расширения LINQ.
Вариант создания стека и помещения всех элементов в стек заключается в использовании рекурсии (и встроенного в систему стека). Вероятно, это не лучший способ работы с производственным кодом, но он послужит лучшим (ИМХО) ответом на собеседовании для следующие причины:
- Это показывает, что вы понимаете рекурсию
- Это меньше кода и выглядит более элегантно
- Наивный интервьюер может не осознавать, что существуют дополнительные расходы (в этом случае вы можете подумать, хотите ли вы там работать).
Что ж, наивным решением было бы отслеживать, на каком узле вы сейчас находитесь, а затем выполнять итерацию с самого начала, пока не найдете этот узел, всегда сохраняя узел, который вы только что покинули.Затем каждый раз, когда вы находите узел, в котором находитесь в данный момент, вы создаете узел, который только что покинули, сохраняете этот узел как тот, в котором находитесь сейчас, а затем повторяете итерацию с самого начала.
Это, конечно, было бы ужасно плохо с точки зрения производительности.
Я уверен, что у более умных людей есть лучшее решение.
Псевдокод (даже с ошибками):
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
Это грязно, но работает:
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;
}
}
Если в программе Explicit Stack мы создаем стек только для данных каждого узла (вместо создания стека типа <Node>, создаём Stack типа <T>) не было бы еще лучше?Потому что тогда нам не нужно хранить какую-либо другую информацию об узле.
IEnumerable<T> Reverse (Node<T> head) {
Stack<T> nodes = new Stack<T>();
while(head != null) {
nodes.Push(head.data);
head = head.Next;
}
while(nodes.Count > 0) {
yield return nodes.Pop();
}
}
вы можете прочитать его за O(n^2) - каждый раз переходить к последнему прочитанному узлу и распечатывать предыдущий
Что случилось с:
public void printBackwards(LinkedList sl){
ListIterator<Element> litr = sl.listIterator(sl.size());
Element temp;
while(litr.previousIndex() >= 0){
temp = litr.previous();
System.out.println(temp);
}
}
Производительность O(n), память O(1) и просто как до-ре-ми!
