Detaillierte Erklärung der Einzelkettenumkehr unter Verwendung von Rekursion und Nichtrekursion

In diesem Artikel wird beschrieben, wie man eine Einzelketteninversion mithilfe von Rekursion und Nichtrekursion erreicht. Es mag viele Schüler geben, die nicht viel darüber wissen, was Einzelketteninversion ist, also lassen Sie uns den Unsinn unterbrechen und kommen Sie direkt zur Sache. Lesen Sie diesen Artikel!
Die Frage gibt Hinweise darauf, dass sowohl rekursive als auch iterative Algorithmen verwendet werden können.
Da ich kein tiefes Verständnis für Rekursion habe, habe ich zuerst die Iteration verwendet, um den Algorithmus zu schreiben. Der Kopfknoten in der Frage wird als der erste Knoten angesehen, der Daten enthält.
Die Idee der Frage: Beginnen Sie am Kopfknoten, gehen Sie rückwärts und folgen Sie der Reihenfolge. Die Umkehrung der Ketten zwischen den Knoten wird nach und nach nacheinander realisiert.
Versuchen Sie zunächst, 2 Zeiger zu verwenden, um den Vorgang abzuschließen, aber es schlägt fehl

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

Der Grund ist wie folgt: Während des Umkehrvorgangs wird head -> next wurde rückgängig gemacht und kann nicht weiter rückwärts durchlaufen. Fügen Sie daher einen Zeiger hinzu und verwenden Sie 3 Zeiger, um den Vorgang abzuschließen Nachdem Sie sich auf „Diskutieren“ bezogen haben, werden Sie es verstehen. Die Idee ist wie folgt: Durch Rekursion wird der Kopfknoten kontinuierlich rückwärts durchlaufen, bis die Beendigungsbedingung erreicht ist: Stoppt nach Erreichen des Schwanzknotens. Der Code lautet wie folgt:

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
};

Der Status wird angezeigt, wenn die rekursive Beendigungsbedingung erreicht ist wie folgt:

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;
};

Der Status nach der Rückkehr zur vorherigen Rekursionsebene ist wie folgt:



Nach dem
Kommentieren 1 und 2 lauten die beiden Codezeilen wie folgt:


Es ist ersichtlich, dass die Position des Kopfknotens mit der Anzahl der Rekursionsebenen zusammenhängt und als Kopfknoten nach der Umkehrung die Position von temp immer unverändert bleibt, wodurch der Umkehreffekt erzielt wird. Obwohl ich rekursiven Code verstehen kann, weiß ich noch nicht, wie ich ihn entwerfen soll, und ich bin noch ein Anfänger.



Verwandte Artikel:

PHP-Implementierung EinzelketteBeispiel für den Tischumdrehvorgang

Das obige ist der detaillierte Inhalt vonDetaillierte Erklärung der Einzelkettenumkehr unter Verwendung von Rekursion und Nichtrekursion. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!