Implementieren Linked List-Umkehrung mit Stack

Question

Ich versuche, eine verknüpfte Liste mit Stack umzukehren.

Node Reverse(Node head) { 
    Stack<Node> x = new Stack<Node>(); 
    Node curr = new Node(); 
    curr= head; 

    while (curr!=null){ 
     x.push(curr); 
     curr=curr.next; 

    } 
    int i=0; 
    while(!x.isEmpty()){ 
     if (i=0){ 
      head=x.pop(); 
      i++; 
     } 
     else{ 
      Node temp = new Node(); 
      temp = x.pop(); 
     } 
    } 
} 

Hier ist mein Code. Ich stecke in der While-Schleife fest. Kannst du bitte helfen.?

Answer 1

Ihr Code unten läuft in einer while-Schleife unendlich.

if (i=0){ 
      head=x.pop(); 
      i++; 
     } 

sollten Sie i=0 ändern i==0

if (i==0){ 
       head=x.pop(); 
       i++; 
      } 

Answer 2

Node Reverse(Node head) { 
    Stack<Node> x = new Stack<Node>(); 
    Node curr = new Node(); 
    curr= head; 

    while (curr!=null){ 
     x.push(curr); 
     curr=curr.next; 

    } 




      Node temp = new Node(); 
      temp=x.pop(); 
      head=temp; 
      x.pop(); 
      while(!x.isEmpty()){ 
      temp = x.pop(); 
       if (x.peek()!=null){ 
      temp.next=x.peek(); 
      } 
       else{ 
        temp.next=null; 
       } 
      x.pop(); 
      temp=temp.next;  

      } 

    return head; 
} 

ich Blei bis hier genommen haben. aber immer noch nicht in der Lage, mit der Ausnahme des leeren Stapels umzugehen.

Dies ist keine endgültige Lösung.

Answer 3

Es gibt mindestens drei Probleme mit dem Code:

• wie erwähnt, i=0 sollte i==0 in Zustand der if Anweisung sein;
• Wenn Sie einen Nicht-Kopf-Knoten vom Stapel entfernen, führen Sie keine Verknüpfung aus; Sie sollten wahrscheinlich etwas wie prev.next = curr sagen, wobei curr und prev in einer offensichtlichen Weise definiert sind;
• Die Funktion ist definiert als Rückgabe eines (Referenz auf) Node; Der Code, den Sie angegeben haben, gibt nichts zurück.

Auch würde ich empfehlen, den folgenden iterativen Ansatz zu verwenden, der einfacher und effizienter ist.

/* ... */ 
typedef struct node_t_ node_t; 

struct node_t_ { 
    node_t *next; 
    int v; 
}; 
/* ... */ 
node_t *reverse(node_t *head) { 
    node_t *curr, *prev, *temp; 

    prev = NULL; 
    curr = head; 
    while (curr != NULL) { 
     temp = curr->next; 
     curr->next = prev; 
     prev = curr; 
     curr = temp; 
    } 

    return prev; 
} 

Ich schrieb den Code in C; Sie sollten keine Probleme haben, es in Java zu konvertieren.

Answer 4

Im Zentrum der Programmierung steht Abstraktion. Sie können Ihren Code wesentlich vereinfachen (und somit einfacher), indem Sie die verknüpfte Liste hinter einer Schnittstelle abstrahieren. Sobald Sie es getan haben, ist die Umkehrung über einen Stapel so einfach wie diese:

void Reverse(LinkedList<T> list) { 
    Stack<T> stack = new Stack<T>(); 

    while (! list.IsEmpty()) 
     stack.Push(list.RemoveFront()); 

    while (! stack.IsEmpty()) 
     list.AppendBack(stack.Pop()); 
} 

Das heißt, denken Sie an Ihrer Liste als eine Einheit mit einer eigenen Schnittstelle, anstatt um vorbei Knoten in Client-Code. Knoten werden nur berührt innerhalb der LinkedList Klasse.