Explication détaillée de l'inversion d'une chaîne unique utilisant la récursion et la non-récursion

Cet article décrit comment réaliser une inversion à chaîne unique en utilisant la récursion et la non-récursion. Il se peut que de nombreux étudiants ne sachent pas grand-chose sur ce qu'est l'inversion à chaîne unique, alors mettons fin aux bêtises. et allez droit au but. Lisez cet article !
La question donne des indications sur le fait que des algorithmes récursifs et itératifs peuvent être utilisés.
Parce que je n'ai pas une compréhension approfondie de la récursivité, j'ai d'abord utilisé l'itération pour écrire l'algorithme. Le nœud principal de la question est considéré comme le premier nœud contenant des données
L'idée de la question : partir du nœud principal, traverser en arrière et suivre l'ordre. L'inversion des chaînes entre les nœuds se réalise progressivement une par une.
Essayez d'abord d'utiliser 2 pointeurs pour terminer l'opération, mais cela échoue

class Solution {
public:       
ListNode* reverseList(ListNode* head) { 
ListNode* pre = NULL;
  while(head -> next)
  {
 pre = head;
 head = head -> next;
 head -> next = pre; 
  }
  return head;
};

La raison est la suivante : pendant le processus d'inversion, dirigez -> next a été inversé et ne peut pas continuer à reculer, alors ajoutez un pointeur et utilisez 3 pointeurs pour terminer l'opération

class Solution {
public:       
ListNode* reverseList(ListNode* head) { 
ListNode* pre = NULL;
  while(head)
  {
 ListNode* next = head -> next;
 head -> next = pre;//head是尾结点，指针置空
 head = next;
 pre = head; 
  }
  return pre;           //head = NULL
};

La récursion ne sera pas travail. Après avoir fait référence à Discuter, vous comprendrez.
L'idée est la suivante : par récursivité, le nœud de tête est continuellement parcouru vers l'arrière jusqu'à ce que la condition de terminaison : s'arrête après avoir atteint le nœud de queue.
Le code est le suivant :

class Solution {
public:       
ListNode* reverseList(ListNode* head) { 
//终止条件，达到尾结点停止
if(head == NULL || head ==NULL)
return head;
else
{
//头结点向后移动
ListNode* temp = reverList(head->next);
head->next->next = head;   //1
head->next = NULL;         //2
}
return temp;
};

Le statut présenté lorsque la condition de terminaison récursive est atteinte est comme suit :




Le statut après retour au niveau de récursivité précédent est le suivant :


Après avoir commenté 1 et 2, les deux lignes de code sont les suivantes :


On peut voir que la position du nœud principal est liée au nombre de niveaux de récursion, et en tant que nœud principal après l'inversion, la position de temp reste toujours inchangée, obtenant ainsi l'effet d'inversion.
Bien que je puisse comprendre le code récursif, je ne sais pas encore comment le concevoir et je suis encore novice.

Articles connexes :

Implémentation PHP Chaîne uniqueExemple d'opération de retournement de table

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!