Exemple de code Java pour implémenter une liste chaînée inversée

Cet article présente principalement l'exemple de code d'implémentation de liste chaînée inversée en langage Java. L'éditeur pense que c'est plutôt bon, je vais donc le partager avec vous ici pour référence des amis qui en ont besoin.

Description du problème

Définissez une fonction qui saisit le nœud principal d'une liste chaînée, inverse la liste chaînée et génère le nœud principal de la liste inversée. Les nœuds de la liste chaînée sont les suivants :

public class ListNode {
  int val;
  ListNode next = null;
  ListNode(int val) {
    this.val = val;
  }
}

Idée 1 :

Pour inverser la liste chaînée, pour le nœud i , nous Pour pointer son prochain vers son prédécesseur, nous devons sauvegarder le nœud prédécesseur. En même temps, si nous avons réaffecté le prochain de i, nous ne pourrons pas trouver le successeur de i. Par conséquent, avant de réaffecter, nous. je dois sauver mon successeur.

Code :

public ListNode ReverseList(ListNode head) {
    if(head == null){
      return null;
    }
    ListNode rHead = null;
    ListNode prior = null;//store prior
    ListNode q = head;//store current
    while(q != null){
      ListNode next = q.next;//store the next
      if(next == null){
        rHead = q;
      }
      q.next = prior;
      prior = q;
      q = next;
    }
    return rHead;
  }

Idée 2 :

Utiliser l'idée de récursivité (je Je n'y ai pas encore pensé, car si la récursivité est utilisée, à chaque fois il devrait être : le premier nœud de la liste chaînée - le pointeur de queue de la liste chaînée renvoyé par récursivité, mais dans ce cas, le pointeur de tête inversé ne peut pas être obtenu.) Réfléchissons-y plus tard.

Résumé

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!