Как читать отдельно связанный список назад?

Question

Один из методов, о котором я могу думать, - это обратить вспять список, а затем прочитать его. Но это связано с изменением плохого списка.
ИЛИ Я могу сделать копию списка, а затем перевернуть его, но это использует дополнительную память O (n). Есть ли лучший способ, который не использует дополнительную память и не изменяет список и работает в O (N) Время

обратный связанный код списка что-то вроде этого в C#

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); 

} 

Answer 1

Чтобы использовать 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; 
    } 
} 

Answer 2

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

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

Я уверен, что у более умных людей есть лучшее решение.

Псевдо-код (с ошибками даже):

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 

Answer 3

вы можете прочитать в O (N^2) - каждый раз, когда идут на последний узел для чтения и печати предыдущего

Answer 4

Действительно, вы должны использовать двусвязный список.

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

Другие варианты, такие как использование рекурсии (эффективное копирование списка в стек), могут привести к выходу из пространства стека, если список слишком длинный.

Answer 5

Если не хватает памяти вы можете полностью изменить список, итерацию по нему и обратной его снова. В качестве альтернативы вы можете сделать стек указателей на узлы (или что-то вроде указателя на C#).

Answer 6

Одна из отличительных черт одноуровневого списка состоит в том, что он, по сути, связан по-отдельности. Это улица с односторонним движением, и нет возможности преодолеть это, если вы не превратите ее во что-то другое (например, обратный односвязный список, стек, двусвязный список ...). Нужно быть верным природе вещей.

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

Answer 7

Это грязно, но работает:

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; 
} 

}

Answer 8

Если предположить, что односвязный список реализует IEnumerable <T>, вы можете использовать обратный метод расширения LINQ в:

var backwards = singlyLinkedList.Reverse(); 

вы 'нужно добавить директиву using System.Linq; в верхней части файла кода, чтобы использовать методы расширения LINQ.

Answer 9

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

1. это показывает, что вы знаток рекурсии
2. это меньше кода и выглядит более элегантно
3. наивный интервьюер не может понять, что есть пространство над головой (если это имеет место вы можете подумать, хотите ли вы там работать).

Answer 10

Существует третье решение, на этот раз с помощью O(log(n)) памяти и O(n log(n)) время, таким образом, занимая промежуточное положение между этими двумя решениями в ответ Марка.

Это эффективно обратный в заказ спуском бинарного дерева [O(log(n))], за исключением того, на каждом шаге вы должны найти в верхней части дерева [O(n)]:

1. Разделить список в двух
2. Recurse во второй половине списка
3. Печать значение в средней точке
4. Recurse в первой половине

Вот решение в 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 

Answer 11

Что случилось с:

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) памяти и просто, как do-re-mi!

Answer 12

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 
} 

Answer 13

Если в Явной программе 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(); 
    } 
}