再帰と非再帰を使用したシングルチェーンリバーサルの詳細な説明

この記事では、再帰と非再帰を使用してシングルチェーン反転を実現する方法について説明します。シングルチェーン反転とは何かを知らない学生も多いかもしれないので、ナンセンスをカットしてこの記事を直接読みましょう。
この質問は、再帰アルゴリズムと反復アルゴリズムの両方を使用できることを示唆しています。
私は再帰について深く理解していないため、最初に反復を使用してアルゴリズムを作成します。
質問のアイデア: から開始します。ヘッドノードを逆方向にトラバースし、ノード間のチェーンの反転を順番に 1 つずつ実装します。
最初に 2 つのポインターを使用して操作を完了しようとしましたが、失敗しました

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

理由は次のとおりです: 反転プロセス中に head ->next が反転され、後方へのトラバースを続けることができないため、ポインターを追加しました操作

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

は再帰的に機能しません。理解するには、ディスカッションを参照してください。
考え方は次のとおりです。再帰により、終了条件 (末尾ノードに到達したら停止) が達成されるまで、先頭ノードが継続的に逆方向にトラバースされます。
コードは次のとおりです:

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

再帰終了条件に到達したときに表示されるステータスは次のとおりです:




再帰の前のレベルに戻った後のステータスは、


passed 1 と 2 の 2 行のコードをコメントした後のステータスは次のようになります


ヘッド ノードの位置が番号に関連していることがわかります。再帰レベルの値と、反転後のヘッド ノードとしての temp は決して移動しないため、反転ターン効果が得られます。 再帰的なコードは理解できましたが、どのように設計すればよいのかはまだ分からず、まだまだ初心者です。

関連記事:

PHP実装シングルチェーンテーブル反転操作例

以上が再帰と非再帰を使用したシングルチェーンリバーサルの詳細な説明の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。