Inverser LinkedList en Java

Question

Je suis à la recherche à la solution dans ce post Reversing a linked list in Java, recursively

J'ai copié le une des solutions ci-dessous. Je l'ai mis en place et ça fonctionne bien.

public ListNode Reverse(ListNode list) 
{ 
    if (list == null) return null; // first question 

    if (list.next == null) return list; // second question 

    // third question - in Lisp this is easy, but we don't have cons 
    // so we grab the second element (which will be the last after we reverse it) 

    ListNode secondElem = list.next; 

    // bug fix - need to unlink list from the rest or you will get a cycle 
    list.next = null; 

    // then we reverse everything from the second element on 
    ListNode reverseRest = Reverse(secondElem); 

    // then we join the two lists 
    secondElem.Next = list; 

    return reverseRest; 
} 

Ce que je ne comprends pas, cependant, ce sont les dernières lignes.

secondElem.next = list; 
return reverseRest; 

Il semble que nous ne retournons pas le secondElem? Mais j'ai débogué à travers le code et on dirait que secondElem est déjà dans reverseRest. Est-ce parce que c'est une référence par valeur dans Java et qu'il est automatiquement mis à jour quand secondElem.Next=list est appliqué?

Answer 1

Si votre objectif est d'inverser simplement la liste, utilisez Collections.reverse(list)

Answer 2

Ne pensez pas à la sémantique passant, penser en termes d'objets dans la mémoire et des variables contenant des références à eux.

état initial:

(list) 
    | 
    V 
[ 1 ] -> [ 2 ] -> ... -> [ N ] 

Après list.next = null;:

(list) (secondElem) 
    |   | 
    V   V 
[ 1 ] [ 2 ] -> ... -> [ N ] 

Après appel récursif:

(list) (secondElem)  (reverseRest) 
    |   |     | 
    V   V     V 
[ 1 ] [ 2 ] <- ... <- [ N ] 

état final après secondElem.Next = list;:

(list) (secondElem)  (reverseRest) 
    |   |     | 
    V   V     V 
[ 1 ] <- [ 2 ] <- ... <- [ N ] 

Answer 3

Ce que je ne comprends pas, cependant, est les dernières lignes.

secondElem.next = liste;
return reverseRest;

Permettez-moi de vous expliquer les 2 lignes que vous ne comprenez pas un par un:

1.secondElem.next = list; 

Je pense que la création de secondElem introduit une complexité supplémentaire. La variable secondElem n'est pas nécessaire du tout.

Au lieu de cela:

// then we reverse everything from the second element on 
    ListNode reverseRest = Reverse(secondElem); 

    // then we join the two lists 
    secondElem.Next = list; 

Utilisez ceci:

ListNode reverseRest = Reverse(list.next);  
list.next.next = list; 

Il est plus facile à saisir. La dernière ligne de code montre clairement le processus d'inversion de liste en soi!

2. return reverseRest; 

Regardez l'utilisation de variables reverseRest & comprendre son but.Son seul but est de percoler la valeur de la queue originale de la liste à la fin de tous les appels de récursivité, de sorte que nous puissions renvoyer la queue originale (qui est aussi la nouvelle tête) à la fonction principale appelée la fonction Inverse. Vous devez comprendre rapidement que nous ne modifions pas du tout la valeur de la variable reverseRest entre les appels de récursion - tout ce que nous recevons comme valeur de retour de Reverse (secondElem) nous le renvoyons "tel quel" de la fonction!