Comment inverser une liste chaînée?

vous inversez la liste de façon itérative et vous avez toujours la liste dans l'intervalle [tête, précédente] correctement inversée(donc courant est le premier noeud qui a son lien mal réglé). À chaque étape, vous faites ce qui suit:

• vous vous souvenez du prochain noeud de courant de sorte que vous pouvez continuer de lui
• vous définissez le lien du courant pour pointer vers le précédent, qui est la bonne direction si vous y pensez
• vous changez précédent pour être à jour, parce que maintenant, actuel a aussi ses liens correctement
• vous changez le premier noeud qui n'a pas son lien correctement défini pour être celui remebered dans la première étape

si vous faites cela pour tous les noeuds que vous pouvez prouver(avec induction par exemple). Que la liste sera inversée correctement.

le code parcourt simplement la liste et inverse les liens jusqu'à ce qu'il atteigne la queue précédente, qu'il renvoie comme nouvelle tête.

Avant:

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

Après:

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

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

je m'appelle "cherry picking". L'idée est de minimiser le nombre de swaps. L'échange se produit entre un indice proche et lointain. C'est un algorithme en 2 passes.

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

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

exemple 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

• Permutation s'applique aux données uniquement, pas pour les pointeurs, les contrôles d'intégrité manquer, mais vous avez l'idée.

Inverser une liste avec un seul lien En utilisant l'itération

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

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

L'idée de base est de détacher le nœud de tête de la première liste et l'attacher à la tête d'une seconde liste. Continuez à répéter jusqu'à ce que la première liste soit vide.

Pseudo:

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 vous souhaitez laisser la liste originale intacte, vous pouvez coder une version copiée récursivement avec l'aide d'une fonction helper.

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

notez que la fonction helper est récursive. Cela signifie que vous pouvez créer une inversion de copie en utilisant itération.

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