チェーンテーブル逆シーケンスアルゴリズム


質問:
チェーンテーブルを指定します.逆順にしてください.すなわち、チェーンテーブルが本来1->2->3->4->5->nullである、逆順後が5->4->3->2->1->nullである.
解法1:反復アルゴリズム
反復アルゴリズムは効率が高いが,コードは再帰アルゴリズムよりやや長い.再帰アルゴリズムはコード量が少ないが,難易度もやや高く,注意深く書かないと書き間違えやすい.
反復アルゴリズムの考え方は,チェーンテーブルを遍歴し,チェーンテーブルノードnextの指向を変更し,遍歴が完了すると,チェーンテーブルの逆順序も完了する.コードは次のとおりです.
struct node {
    int data;
    struct node* next;
};
typedef struct node* pNode;
pNode reverse(pNode head)
{
    pNode current = head;
    pNode next = NULL, result = NULL;
    while (current != NULL) {
        next = current->next;
        current->next = result;
        result = current;
        current = next;
    }
    return result;
}
値を返さなければ、パラメータをポインタのポインタに変更し、チェーンテーブルのヘッダノード値を直接変更することができます(C++で参照を直接渡すほうが便利です).次のコードを書くことができます.
void reverse2(struct node** headRef)
{   
    pNode current = *headRef;
    pNode next = NULL, result = NULL;
    while (current != NULL) {
        next = current->next;
        current->next = result;
        result = current;
        current = next;
    }
    *headRef = result;
}

解法2:再帰アルゴリズム
再帰アルゴリズムの実現原理:元のチェーンテーブルが1,2,3,4であると仮定すると、まず逆シーケンスの後の2,3,4が4,3,2になり、その後ノード1を逆シーケンスの4,3,2の後にリンクし、4,3,2,1を形成し、チェーンテーブル全体の逆シーケンスを完了する.コードは次のとおりです.
void reverseRecur(struct node** headRef)
{
    if (*headRef == NULL)  return;
    pNode first, rest;
    first = *headRef;       //  first={1,2,3,4}
    rest = first->next;   // rest={2,3,4}
    if (rest == NULL) return;
    reverseRecur(&rest); //rest     {4,3,2}
    first->next->next = first; //               
    first->next = NULL;
    *headRef = rest;  //     
}

C++の参照タイプを使用すると、コードは少し単純になります.コードは次のとおりです.
void reverseRecur(pNode& p)
{
if (!p) return;
 pNode rest = p->next;
  if (!rest) return;
  reverseRecur(rest);
  p->next->next = p;
  p->next = NULL;
  p = rest;
}