¿Cómo leer una lista unida de forma simple al revés?

Question

Un método que se me ocurre es invertir la lista y luego leerla. Pero esto implica cambiar la lista que es mala.
O puedo hacer una copia de la lista y luego invertirla, pero esto usa memoria O (n) adicional. ¿Hay algún método mejor que no utiliza memoria adicional y no modifica la lista y se ejecuta en O (n) tiempo

invertir el código de lista enlazada es algo como esto en 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; 

} 

recursiva solución es

void ReadBackWard (Node n) 
{ 
    if (n==null) 
     return; 
    else 
     ReadBackward(n.Next); 

    Console.WriteLine(n.Data); 

} 

Answer 1

Para usar la memoria O (n) y el rendimiento de O (n), cree una pila; empuja todo mientras iteras en la dirección de avance, luego apaga todo, produciendo los resultados.

Para usar el rendimiento O (n^2) (pero O (1) memoria extra), léelo hacia adelante cada vez, hasta el nodo antes de la última vez que tenga acceso.

Ejemplo:

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

Bueno, la solución ingenua sería hacer un seguimiento de qué nodo que está actualmente en, a continuación, repetir desde el principio hasta que encuentre ese nodo, siempre salvando el nodo que acaba de salir. Luego, cada vez que encuentre el nodo en el que se encuentra actualmente, producirá el nodo que acaba de dejar, guardará ese nodo como el que está actualmente y luego volverá a iterar desde el principio.

Esto, por supuesto, sería terriblemente malo en cuanto a rendimiento.

Estoy seguro de que algunas personas más inteligentes tienen una mejor solución.

Pseudo-código (incluso con los insectos):

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

se podía leer en O (n^2) - cada vez que vaya al último nodo leer e imprimir la anterior

Answer 4

Realmente deberías estar usando una lista doblemente vinculada.

Si esto no es posible, creo que su mejor opción será construir una copia de la lista que se ha invertido.

Otras opciones, como confiar en la recursión (copiar efectivamente la lista a la pila) podría hacer que se quede sin espacio en la pila si la lista es demasiado larga.

Answer 5

Si corta lista de la memoria se puede revertir, iterar sobre ella una y otra vez revertirla. Alternativamente, puede hacer una pila de punteros a nodos (o lo que sea como un puntero en C#).

Answer 6

Una de las características de una lista de enlace único es que, de hecho, está vinculada de forma individual. Es una calle de un solo sentido, y no hay forma de superarlo a menos que la conviertas en otra cosa (como una lista invertida de enlace único, una pila, una lista doblemente vinculada ...). Uno debe ser fiel a la naturaleza de las cosas.

Como se ha señalado anteriormente; si necesita recorrer una lista en ambos sentidos; necesitas tener una lista doblemente vinculada. Esa es la naturaleza de una lista doblemente vinculada, va en ambos sentidos.

Answer 7

Ésta es desordenado, pero funciona:

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

Asumiendo que su lista simplemente enlazada implementa IEnumerable <T>, puede utilizar el método de extensión inversa de LINQ:

var backwards = singlyLinkedList.Reverse(); 

Usted Necesitará agregar una directiva using System.Linq; en la parte superior del archivo de código para usar los métodos de extensión de LINQ.

Answer 9

Una variación de crear una pila y empujar todos los elementos a la pila es recursion (y la pila integrada en el sistema), probablemente esta no sea la manera de ir con el código de producción pero sirve como mejor (IMHO) respuesta entrevista por las siguientes razones:

1. demuestra que grok recursividad
2. es menos código y aparece más elegante
3. un entrevistador ingenua puede no darse cuenta de que hay una sobrecarga de espacio (si este es el caso es posible que desee considerar si desea trabajar allí).

Answer 10

Hay una tercera solución, esta vez utilizando O(log(n)) memoria y O(n log(n)) tiempo, ocupando así el término medio entre las dos soluciones en la respuesta de Marc.

Es efectivamente un inverso de descenso en la orden de un árbol binario [O(log(n))], excepto en cada paso que necesita para encontrar la parte superior del árbol [O(n)]:

1. Dividir la lista en dos
2. Recursividad en la segunda mitad de la lista
3. Imprimir el valor en el punto medio
4. Recursividad en la primera mitad

Aquí está la solución en Python (no sé 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) 

Esto podría ser reformulada usando iteración en lugar de recursividad, pero a costa de una mayor claridad.

Por ejemplo, para obtener una lista de un millón de entrada, las tres soluciones toman en el orden de:

 
Solution Memory  Performance 
========================================= 
MarC#1  4MB 1 million operations 
    Mine  80B 20 million operations 
MarC#2  4B 1 trillion operations 

Answer 11

¿Qué pasa con:

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 rendimiento (n), O (1) memoria y simple como 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

Si en el programa de pila explícita, creamos una pila de sólo los datos de cada nodo (en lugar de crear la pila de tipo <Node>, creamos Pila de tipo <T>) ¿no sería aún mejor? Porque no necesitamos almacenar ninguna otra información del Nodo entonces.

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