Opérations couramment utilisées sur les listes chaînées - explication détaillée de l'inversion

Opérations couramment utilisées sur les listes chaînées - inversion

Définissons d'abord une classe de nœuds pour une liste chaînée unique

public class ListNode {2         
int val;3         ListNode next = null;// 指向的下个节点4 5         
ListNode(int val) {6             this.val = val;7         }8     
}

Implémentation une liste à chaînage unique Il existe deux méthodes d'inversion

1. Utiliser la récursivité et l'inversion de l'arrière vers l'avant. Commencez par le nœud de tête, recherchez en arrière jusqu'à ce que vous trouviez le nœud de queue, puis commencez à inverser. ​

 1     public ListNode reverseList(ListNode head) { 2         
 if (head == null || head.next == null) 3             return head; 4  5         
 ListNode prev = reverseList(head.next);// 递归调用,先反转下个节点 6  7         
 head.next.next = head;// 将当前结点的指针域指向前一结点 8         
 head.next = null;// 前一结点的指针域令为null; 9         
 return prev;// 反转后新链表的头结点10     
 }

2. Utilisez la traversée et l'inverse d'avant en arrière. Enregistrez d'abord le nœud suivant, puis pointez le nœud actuel vers le nœud précédent, puis déplacez le nœud vers le bas pour continuer le cycle pour la prochaine inversion.

 1     public ListNode reverseList(ListNode head) { 2         if (head == null) { 3             
 return null; 4         } 5         ListNode pre = null; 6         
 ListNode next = null; 7         while (head != null) { 8             
 // 保存下个节点,防止丢失 9             next = head.next;10             
 // 将他的下个节点指向前个节点11             head.next = pre;12 13             
 // head指向pre后，就继续依次反转下个节点14             
 // 让pre，head依次向后移动一个节点，继续下一次的反转15             
 pre = head;16             head = next;17         }18         
 return pre;19     
 }

Dès que j'ai terminé la programmation en ligne, je l'ai enregistrée pour une référence facile dans le futur.

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!