Comment inverser une liste chaînée?

Vous inversez la liste de manière itérative et toujours avoir la liste dans l'intervalle [tête, précédente] correctement inversé(donc le courant est le premier nœud qui a son lien n'est pas réglée correctement). Sur chaque étape de la manière suivante:

• Vous rappelez-vous le prochain nœud de courant de sorte que vous pouvez continuer à partir de ce
• Vous définissez le lien de courant pointant vers précédent, qui est le bon sens si vous pensez à ce sujet
• Vous changer précédente pour être courant, parce que maintenant, actuel a aussi ses liens correctement
• Vous modifier le premier nœud qui n'est pas hae son lien correctement réglé pour être l'un remebered dans la première étape

Si vous faites cela pour tous les nœuds que vous pouvez prouver(avec l'induction, par exemple). Que la liste doit être correctement inversée.

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

Renverser une seule liste liée à l'aide de 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

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 le premier de la liste est vide.

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

Si vous voulez quitter la liste d'origine intact, alors vous pouvez coder une copie de la version récursive avec l'utilisation d'une fonction d'assistance.

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

Noter que la fonction d'assistance est la queue récursive. Cela signifie que vous pouvez créer une copie de renversement à l'aide d'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

La façon la plus simple de penser qu'il est à penser comme cela:

1. D'abord ajouter la tête de la liste pour une nouvelle liste liée.
2. Garder une itération dans l'original, et continuez d'ajouter les nœuds avant de la tête de la nouvelle liste liée.

Diagramme:

D'abord:

Original List -> 1 2 3 4 5
New List -> null

1ère Itération

Original List -> 1 2 3 4 5
New List -> 1->null [head shifted to left, now newHead contains 1 and points to null]

2ème Itération

Original List -> 1 2 3 4 5
New List -> 2-> 1->null [head shifted to left, now newHead contains 2 and points to next node which is 1]

3ème Itération

Original List -> 1 2 3 4 5
New List ->3 -> 2-> 1->null [head shifted to left, now newHead contains 2 and points to next node which is 1]

Maintenant, il continue en boucle jusqu'à la fin. Donc, finalement, la nouvelle liste devient:

  New List->  5 -> 4 -> 3 -> 2 -> 1 -> null

Le code pour la même chose devrait être comme ceci (il est facile à comprendre):

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */

public ListNode reverseList(ListNode head) {
    if(head == null) {
        return null;
    }

    if(head.next == null) {
        return head;
    }

    ListNode current = head;
    ListNode previous = new ListNode(head.val);
    previous.next = null;

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

    return previous;
}

private ListNode addBeforeHead(ListNode node, ListNode head) {
    if (node == null) return null;
    ListNode temp = new ListNode(node.val);

    temp.next = head;
    head = temp;

    return head;
}