Come invertire una lista collegata?

Question

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

Come è esattamente l'inversione dell'elenco? Ho capito che per prima cosa imposta il secondo nodo su forward. Quindi dice che current.next è uguale a un nodo nullprevious. Quindi dice che previous è ora current. Infine current diventa forward?

Non riesco a capire questo e come il suo rovesciamento. Qualcuno può spiegare come funziona?

Answer 1

Si inverte l'elenco in modo iterativo e si ha sempre l'elenco nell'intervallo [testa, precedente] correttamente invertito (quindi corrente è il primo nodo che ha il suo collegamento non impostato correttamente). Ad ogni passo che fai la seguente:

• Vi ricordate il successivo nodo di corrente in modo da poter continuare da esso
• Si imposta il link di corrente da punta al precedente, che è la direzione giusta, se si pensarci
• si cambia precedente di essere attuale, perché la società attuale ha anche il suo legame impostato correttamente
• si modifica il primo nodo che non HAE suo legame impostato correttamente essere quello si ricordava sempre nella prima fase

Se lo fai per tutti i nodi puoi provare (con induzione per esempio). Che la lista sarà correttamente invertita.

Answer 2

Il codice sposta semplicemente l'elenco e inverte i collegamenti fino a raggiungere la coda precedente, che restituisce come nuova testa.

Prima:

Node 1 (Head) -> Node 2 -> Node 3 -> Node 4 (Tail) -> null 

Dopo:

null <- Node 1 (Tail) <- Node 2 <- Node 3 <- Node 4 (Head) 

Answer 3

Answer 4

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

Answer 5

Io lo chiamo "cherry picking". L'idea è di ridurre al minimo il numero di scambi. Lo scambio avviene tra un indice vicino e lontano. È un algoritmo a 2 passaggi.

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

Esempio 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. 

Esempio 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 si applica ai dati solo, per non puntatori, ci potrebbero essere eventuali controlli di integrità mancati , ma hai avuto l'idea.

Answer 6

inverte una lista semplicemente concatenata utilizzando iterazione

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 

Answer 7

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

Answer 8

L'idea di base è quella di staccare il nodo testa dal primo elenco e fissarlo alla testa di un secondo elenco. Continua a ripetere finché il primo elenco non è vuoto.

Pseudocodice:

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 

Se si desidera lasciare la lista originale indisturbati, allora è possibile codificare una versione di copia in modo ricorsivo con l'uso di una funzione di supporto.

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 

Si noti che la funzione di supporto è in coda ricorsiva. Ciò significa che è possibile creare un'inversione di copia usando l'iterazione.

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