リンクリストを逆転させるための再帰的解答

Question

void recursiveReverse(struct node** head_ref) 
{ 
struct node* first; 
struct node* rest; 

/* empty list */ 
if (*head_ref == NULL) 
    return; 

/* suppose first = {1, 2, 3}, rest = {2, 3} */ 
first = *head_ref; 
rest = first->next; 

/* List has only one node */ 
if (rest == NULL) 
    return; 

/* reverse the rest list and put the first element at the end */ 
recursiveReverse(&rest); 
first->next->next = first; 

/* tricky step -- see the diagram */ 
first->next = NULL;   

/* fix the head pointer */ 
*head_ref = rest;    
} 

上記のコードは再帰的にリンクリストを逆転させるためのコードです。私はプログラムを理解しましたが、最後に* head_ref = rest;私を混乱させている。私はそれを詳しく説明しましょう。

>の1-の例を見てみましょう2 - > 3

in first recursion: first=1, rest=2 
in second recursion: first=2, rest=3 
in last recursion: first=3, rest=null 

と、その時点から、我々は戻って、各ステップで私たちが割り当て* headRef = が最終的に私たちは私たちの最初のステップで戻ってきて休みます残りは2であり、私達は* headRef = 2 を割り当てるが、我々は

私を助けてください、私はアドレスを印刷してみました私は、私はここで何かをしないのです確信しているが、私はこの問題を解決することができませんでした3ない2 に、残りのポイントが必要最初と残りのimage shows that after recursion, address of rest doesn't change

ありがとうございます。

上記のコードはgeeksforgeeksのものです...私はコメントしましたが、誰も私を助けませんでした。

http://imgur.com/Dfb46xD

Answer 1

restポインタのアドレスが再帰呼び出しで渡されることに注意してください。

再帰から戻るときに、restポインタが 'remaining-list'の 'new'開始点を指すように変更されます。

これは、あなたの例では、各逆方向再帰ステップでrestが要素3を指すように変更されることを意味します。