Pourquoi ne puis-je pas simplement faire node = node.next pour parcourir la liste chaînée?

Question

Je suis en train de faire un Problème d'Interview Cracking the Coding (2.4) et je suis supposé partitionner une liste chaînée autour d'une valeur x, de sorte que tous les nœuds inférieurs à x viennent avant tous les nœuds supérieurs ou égaux à x. Cependant, je suis vraiment confus quant aux raisons pour lesquelles une variable temporaire "next" est nécessaire et pourquoi node.next est annulé en dessous. Pourquoi ne puis-je pas simplement faire node = node.next à la fin de la boucle while?

Je crée simplement deux listes liées, avant et après, et je les fusionne une fois que les valeurs correctes sont entrées dans chaque liste.

public static Node partition(Node node, int x) { 
    Node beforeStart = null; 
    Node beforeEnd = null; 
    Node afterStart = null; 
    Node afterEnd = null; 

    /* Partition list */ 
    while (node != null) { 
     Node next = node.next; 
     node.next = null; 
     if (node.data < x) { 
      if (beforeStart == null) { 
       beforeStart = node; 
       beforeEnd = beforeStart; 
      } else { 
       beforeEnd.next = node; 
       beforeEnd = beforeEnd.next; 
      } 
     } else { 
      if (afterStart == null) { 
       afterStart = node; 
       afterEnd = afterStart; 
      } else { 
       afterEnd.next = node; 
       afterEnd = afterEnd.next; 
      } 
     } 
     node = next;  
    } 

    /* Merge before list and after list */ 
    if (beforeStart == null) { 
     return afterStart; 
    } 

    beforeEnd.next = afterStart; 
    return beforeStart; 
} 

Answer 1

Pourquoi je ne peux pas faire juste noeud = node.next à la fin de la boucle while?

Cela peut être fait de cette façon. Après avoir fait la partition, pour chaque liste, vous devez définir le pointeur suivant du dernier nœud sur NULL. Cela prendra juste deux lignes de code.

L'exemple de code utilise next = node.next et node.next = NULL pour terminer chaque liste au cours du processus de partition, mais dans ce cas, ce n'est pas nécessaire, car les listes n'ont pas besoin de terminaisons NULL avant la partition le processus est terminé.

Answer 2

La boucle de votre question supprime les nœuds de la tête de la liste d'origine et les ajoute à la liste avant ou après, jusqu'à ce que la liste d'origine soit vide. Ensuite, il concatène les listes avant et après.

C'est facile à expliquer et à comprendre.

Il peut se faire sans l'next ou à node.next temporaire annulant à chaque itération, mais la description ci-dessus ne s'appliquerait plus - nœuds ne seraient pas retirés de la liste initiale à chaque itération, la liste avant et après la liste ne contiendrait pas seulement les nœuds appropriés, l'opération que vous effectuez sur ces nœuds n'est pas "en cours d'ajout", et les nœuds apparaîtraient même dans plusieurs listes pendant un certain temps.

Votre algorithme serait soudainement beaucoup plus difficile à décrire et à comprendre. C'est une mauvaise chose dans le développement de logiciels, et une mauvaise chose dans une interview de codage.