¿Cómo revertir una lista vinculada?

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

¿Cómo está exactamente invirtiendo la lista? Me da que primero establece el segundo nodo en forward. Entonces dice current.next es igual a null nodo previous. Entonces dice previous ahora es current. Por último current se convierte en forward?

Parece que no capto esto y cómo se invierte. ¿Alguien puede explicar cómo funciona esto?

Answer 1

Invierta la lista de forma iterativa y siempre tenga la lista en el intervalo [cabeza, anterior] correctamente invertida (por lo que el primer nodo que tiene su enlace no está configurado correctamente). En cada paso de hacer lo siguiente:

• usted recuerda el siguiente nodo de la corriente para que pueda continuar de la misma
• definido el vínculo de la corriente que se va señalando anterior, que es la dirección correcta si pensar en ello
• cambias anterior a ser actual, porque ahora actual también tiene su enlace ajustado correctamente
• cambia el primer nodo que no hae su vínculo establecido correctamente para ser el remebered en el primer paso

Si haces eso para todos los nodos, puedes probarlo (con inducción, por ejemplo). Que la lista se invertirá correctamente.

Answer 2

El código simplemente recorre la lista e invierte los enlaces hasta que alcanza la cola anterior, que devuelve como la nueva cabeza.

Antes:

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

Después:

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

llamo "cherry picking". La idea es minimizar el número de intercambios. El intercambio ocurre entre un índice cercano y uno lejano. Es un algoritmo de 2 pases.

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

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

Ejemplo 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 aplica a los datos solamente, no a los punteros, puede haber cualquier comprobaciones de validez perdidas , pero tienes la idea.

Answer 6

Invertir una lista enlazada usando iteración

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

La idea básica es la de separar el nodo de cabecera de la primera lista y adjuntarlo a la cabeza de una segunda lista. Sigue repitiendo hasta que la primera lista esté vacía.

Pseudocódigo:

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 

Si desea salir de la lista original no perturbado a continuación, puede codificar una versión de copia de forma recursiva con el uso de una función de ayuda.

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 

Tenga en cuenta que la función auxiliar es recursiva de cola. Esto significa que puede crear una inversión de copiado mediante iteración.

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