Inversión de la lista vinculada única en C#

Question

Estoy intentando invertir una lista vinculada. Este es el código que se me ocurrió:

public static void Reverse(ref Node root) 
{ 
     Node tmp = root; 
     Node nroot = null; 
     Node prev = null; 

     while (tmp != null) 
     { 
      //Make a new node and copy tmp 
      nroot = new Node();  
      nroot.data = tmp.data; 

      nroot.next = prev; 
      prev = nroot; 
      tmp = tmp.next; 
     } 
     root = nroot;    
    } 

Está funcionando bien. Me preguntaba si sería posible evitar la creación de un nuevo nodo. Me gustaría tener sugerencias sobre esto.

Answer 1

Node p = root, n = null; 
while (p != null) { 
    Node tmp = p.next; 
    p.next = n; 
    n = p; 
    p = tmp; 
} 
root = n; 

Answer 2

¿Por qué no tener simplemente el punto de cabeza en la cola, el punto de cola en la cabeza, y pasar por la lista invirtiendo la dirección en la cual los puntos previos?

Si no está utilizando una cabeza y una cola, simplemente revise la lista invirtiendo las relaciones previas, y luego diríjase a la que tenía un valor nulo anterior cuando llegó a ella.

Answer 3

No necesita hacer una copia. Algunos pseudo código:

prev = null; 
current = head; 
next = current->next; 

(while next != null) 
    current->next=prev 
    prev=current 
    current=next 
    next=current->next 

Answer 4

Esa pregunta se hace mucho. Cuando me lo preguntaron en mis entrevistas hace muchos años, razoné de la siguiente manera: una lista con un solo enlace es esencialmente una pila. Revirtiendo una lista enlazada, por tanto, es una operación trivial en pilas:

newList = emptyList; 
while(!oldList.IsEmpty()) 
    newList.Push(oldList.Pop()); 

Ahora todo lo que tiene que hacer es poner en práctica IsEmpty y Push y Pop, que son una o dos líneas como máximo.

Lo escribí en unos veinte segundos y el entrevistador parecía algo perplejo en ese momento. Creo que esperaba que yo tomara unos veinte minutos para hacer unos veinte segundos de trabajo, lo que siempre me ha parecido extraño.

Answer 5

La definición de la referencia no es necesario porque si se hace el nodo como un tipo de referencia, que está bien hacer:

public static void Reverse(Node root) 

Además, la belleza de la pregunta de la entrevista es menor consumo de memoria y en su lugar inversión. Tal vez también se le pida una forma recursiva de hacerlo. Hace

Answer 6

public Node ReverseList(Node cur, Node prev) 
    { 
     if (cur == null) // if list is null 
      return cur; 

     Node n = cur.NextNode; 
     cur.NextNode = prev; 
     return (n == null) ? cur : ReverseList(n, cur); 
    } 

Answer 7

años me perdí una posición desarrollador ASP.NET MVC hipster-LA-entretenimiento de la compañía porque no podía responder a esta pregunta :((Es una manera de eliminar a los mayores no en la ciencia informática.) así que estoy avergonzado de admitir que me tomó demasiado tiempo para resolver esto en LINQPad según los días reales LinkedList<T>:.

var linkedList = new LinkedList<int>(new[]{1,2,3,4,5,6,7,8,9,10}); 
linkedList.Dump("initial state"); 

var head = linkedList.First; 
while (head.Next != null) 
{ 
    var next = head.Next; 
    linkedList.Remove(next); 
    linkedList.AddFirst(next.Value); 
} 

linkedList.Dump("final state"); 

el sólo lectura LinkedListNode<T>.Next propiedad es lo que hace LinkedList<T> tan importante aquí (no comp -la gente de ciencia se anima a estudiar la historia de las estructuras de datos --- se supone que debemos hacernos la pregunta, ¿dónde está el linked list vienen de --- ¿por qué existe?)

Answer 8

Aquí hay un código de muestra para revertir una lista vinculada.

usando Sistema;

class Program 
{ 
    static void Main(string[] args) 
    { 
     LinkItem item = generateLinkList(5); 
     printLinkList(item); 
     Console.WriteLine("Reversing the list ..."); 
     LinkItem newItem = reverseLinkList(item); 
     printLinkList(newItem); 
     Console.ReadLine(); 
    } 

    static public LinkItem generateLinkList(int total) 
    { 
     LinkItem item = new LinkItem(); 
     for (int number = total; number >=1; number--) 
     { 
      item = new LinkItem 
      { 
       name = string.Format("I am the link item number {0}.", number), 
       next = (number == total) ? null : item 
      }; 
     } 
     return item; 
    } 

    static public void printLinkList(LinkItem item) 
    { 
     while (item != null) 
     { 
      Console.WriteLine(item.name); 
      item = item.next; 
     } 
    } 

    static public LinkItem reverseLinkList(LinkItem item) 
    { 
     LinkItem newItem = new LinkItem 
     { 
      name = item.name, 
      next = null 
     }; 

     while (item.next != null) 
     { 
      newItem = new LinkItem 
      { 
       name = item.next.name, 
       next = newItem 
      }; 

      item = item.next; 
     } 

     return newItem; 
    } 
} 

class LinkItem 
{ 
    public string name; 
    public LinkItem next; 
} 

Answer 9

Complexity O (n + m).Suponiendo que la cabeza está el nodo de inicio:

List<Node>Nodes = new List<Node>(); 
Node traverse= root; 
while(traverse!=null) 
{  
     Nodes.Add(traverse); 
     traverse = traverse.Next; 

} 

int i = Nodes.Count - 1;  
root = Nodes[i]; 
for(; i>0; i--) 
{ 
    Nodes[i].Next = Nodes[i-1]; 
} 
Nodes[0].Next=null; 

Answer 10

lista enlazada reversión recursiva

using System; 
using System.Collections.Generic; 
using System.Linq; 
using System.Text; 
using System.Threading.Tasks; 

namespace ReverseLinkedList 
{ 
    class Program 
    { 
     static void Main(string[] args) 
     { 
      Node head = null; 
      LinkedList.Append(ref head, 25); 
      LinkedList.Append(ref head, 5); 
      LinkedList.Append(ref head, 18); 
      LinkedList.Append(ref head, 7); 

      Console.WriteLine("Linked list:"); 
      LinkedList.Print(head); 

      Console.WriteLine(); 
      Console.WriteLine("Reversed Linked list:"); 
      LinkedList.Reverse(ref head); 
      LinkedList.Print(head); 

      Console.WriteLine(); 
      Console.WriteLine("Reverse of Reversed Linked list:"); 
      LinkedList.ReverseUsingRecursion(head); 
      head = LinkedList.newHead; 
      LinkedList.PrintRecursive(head); 
     } 

     public static class LinkedList 
     { 
      public static void Append(ref Node head, int data) 
      { 
       if (head != null) 
       { 
        Node current = head; 
        while (current.Next != null) 
        { 
         current = current.Next; 
        } 

        current.Next = new Node(); 
        current.Next.Data = data; 
       } 
       else 
       { 
        head = new Node(); 
        head.Data = data; 
       } 
      } 

      public static void Print(Node head) 
      { 
       if (head == null) return; 
       Node current = head; 
       do 
       { 
        Console.Write("{0} ", current.Data); 
        current = current.Next; 
       } while (current != null); 
      } 

      public static void PrintRecursive(Node head) 
      { 
       if (head == null) 
       { 
        Console.WriteLine(); 
        return; 
       } 
       Console.Write("{0} ", head.Data); 
       PrintRecursive(head.Next); 
      } 

      public static void Reverse(ref Node head) 
      { 
       if (head == null) return; 
       Node prev = null, current = head, next = null; 
       while (current.Next != null) 
       { 
        next = current.Next; 
        current.Next = prev; 
        prev = current; 
        current = next; 
       } 
       current.Next = prev; 
       head = current; 
      } 

      public static Node newHead; 

      public static void ReverseUsingRecursion(Node head) 
      { 
       if (head == null) return; 
       if (head.Next == null) 
       { 
        newHead = head; 
        return; 
       } 

       ReverseUsingRecursion(head.Next); 
       head.Next.Next = head; 
       head.Next = null; 
      } 
     } 

     public class Node 
     { 
      public int Data = 0; 
      public Node Next = null; 
     } 
    } 
}