Wie man eine verkettete Liste umkehrt?

 Node reverse(Node head) {
    Node previous = null;
    Node current = head;
    Node forward;

    while (current != null) {
        forward = current.next;
        current.next = previous;
        previous = current;
        current = forward;
    }

    return previous;
}

Wie genau ist es die Umkehrung der Liste? Ich verstehe, dass es setzt zuerst den zweiten Knoten zu forward. Dann heißt es current.next gleich ein null Knoten previous. Dann heißt es previous ist jetzt current. Schließlich current wird forward?

Ich kann nicht scheinen zu begreifen, und wie seine Umkehrung. Kann mir bitte jemand erklären, wie das funktioniert?

InformationsquelleAutor der Frage user1176235 | 2012-01-31

38

InformationsquelleAutor der Antwort Aquarius_Girl
3

Kehren Sie die Liste iterativ und immer haben die Liste in das Intervall [Kopf, vorige] richtig-Umgekehrt(also aktuelle ist der erste Knoten, dessen link nicht richtig gesetzt). Auf jedem Schritt, den Sie tun, die folgenden:
- Sie erinnern sich an den nächsten Knoten der aktuellen, so dass Sie weiterhin von ihm
- Setzen Sie den link Aktueller zu sein, zeigt auf das vorhergehende, das ist die richtige Richtung, wenn man darüber nachdenkt
- Sie ändern vorhergehenden aktuell sein, da jetzt aktuelle hat auch seinen link richtig gesetzt
- Ändern Sie den ersten Knoten, der nicht hae seinen link richtig gesetzt zu sein, der remebered, die im ersten Schritt
Wenn Sie tun, dass für alle Knoten, die Sie belegen kann(mit Induktion zum Beispiel). Dass die Liste korrekt rückgängig gemacht.

InformationsquelleAutor der Antwort Ivaylo Strandjev
3

Den code einfach geht die Liste und dreht die links bis Sie die Vorherige Rute, die es gibt, wie der neue Leiter.

Bevor:
```
Node 1 (Head) -> Node 2 -> Node 3 -> Node 4 (Tail) -> null
```
Nach:
```
   null <- Node 1 (Tail) <- Node 2 <- Node 3 <- Node 4 (Head)
```
InformationsquelleAutor der Antwort Michael Borgwardt

public Node getLastNode( )
{
    if( next != null )
        return next.getLastNode( );
    else
        return this;
}

public Node reverse( Node source )
{
    Node reversed = source.getLastNode( );
    Node cursor = source;

    while( cursor != reversed )
    {
        reversed.addNodeAfter( cursor.getInfo( ) );
        cursor = cursor.getNodeAfter( );
    }

    source = reversed;
    return source;
}

InformationsquelleAutor der Antwort user2507212

Ich nenne es "cherry picking". Die Idee ist die Minimierung der Anzahl der swaps. Swapping passiert, zwischen nah und fern-index. Seine 2-Pass Algorithmus.

    (Odd length)  A -> B -> C -> D -> E
    (Even length) A -> B -> C -> D

    Pre-Condition: N >= 2

    Pass 1: Count N, the number of elements

    Pass 2: 
            for(j=0 -> j<= (N/2 -1))
            {
              swap(j, (N-1)-j)
            }

Beispiel 1:

   For above Odd length list, N = 5 and there will be two swaps 

      when j=0, swap(0, 4) //post swap state: E B C D A
      when j=1, swap(1, 3) //post swap state: E D C B A


   The mid point for odd length lists remains intact.

Beispiel 2:

   For above Even length list, N = 4 and there will be two swaps 

      when j=0, swap(0, 3) //post swap state: D B C A
      when j=1, swap(1, 2) //post swap state: D C B A

Swapping gilt für Daten, nicht für Zeiger, die es vielleicht irgendwelche Plausibilitätsprüfungen verpasst, aber Sie bekommen die Idee.

InformationsquelleAutor der Antwort NitinS

Rückwärtsfahren eine einfach verkettete Liste mittels iteration

current = head //point current pointer to head of the linked list

while(current != NULL)
{
forward = current->link; //point to the next node
fforward = forward->link; //point the next node to next node
fforward->link = forward;//1->2->3,,,,,,,,,this will point node 3 to node 2
forward->link = current; //this will point node 2 to node 1
if(current == head)
current->link = NULL;//if current pointer is head pointer it should point to NULL while reversing

current = current->link; //traversing the list
}
head = current; //make current pointer the head pointer

InformationsquelleAutor der Antwort Nanobrains

  list_t *reverse(list_t *a)
  {
    list_t *progress = NULL;
    while(a)
    {
      list_t *b; //b is only a temporary variable (don't bother focusing on it)
      b = a->next;
      a->next = progress; //because a->next is assigned to another value, we must first save a->next to a different variable (to be able to use it later)
      progress = a; //progress is initially NULL (so a->next = NULL (because it is the new last element in the list))
      a = b; //we set a to b (the value we saved earlier, what a->next was before it became NULL)
      /*
        now, at next iteration, progress will equal a, and a will equal b.
        so, when I assign a->next = progress, I really say, b->next = a.
        and so what we get is: b->a->NULL.
        Maybe that gives you an idea of the picture?
        What is important here is:
          progress = a
        and
          a = b
        Because that determines what a->next will equal:
          c->b->a->0
        a's next is set to 0
        b's next is set to a
        c's next is set to b
      */
    }
    return progress;
  }

InformationsquelleAutor der Antwort 010101010101kakaka92

Die grundlegende Idee ist, zu trennen von dem head-Knoten aus der ersten Liste und hängen Sie es an den Kopf der zweiten Liste. Wiederholt dies, bis die erste Liste leer ist.

Pseudocode:

function reverseList(List X) RETURNS List
   Y = null
   WHILE X <> null
      t = X.next
      X.next = Y
      Y = X
      X = t
   ENDWHILE
   RETURN Y
ENDfunction

Wenn Sie möchten, können Sie die ursprüngliche Liste ungestört, dann können Sie den code kopieren version rekursiv mit der Verwendung einer Hilfsfunktion.

function reverseList(List X) RETURNS List
   RETURN reverseListAux(X, null)
ENDfunction

function reverseListAux(List X, List Y) RETURNS List
   IF X = null THEN
       RETURN Y
   ELSE
       RETURN reverseListAux(X.next, makeNode(X.data, Y))
ENDfunction

Beachten Sie, dass die Helfer-Funktion tail-rekursiv. Dies bedeutet, dass können Sie erstellen, kopieren Umkehrung mittels iteration.

function reverseList(List X) RETURNS List
   Y = null
   WHILE X <> null
     Y = makeNode(x.data, Y)
     X = X.next   
   ENDWHILE
   RETURN Y
ENDfunction

InformationsquelleAutor der Antwort Gregory Schoenmakers

Schreibe einen Kommentar

Du musst angemeldet sein, um einen Kommentar abzugeben.