不理解代碼片斷，使用C中的遞歸反轉鏈接列表

Question

void reverse(LIST **head) 
{ 
    if(!*head) 
     return ; 

    LIST *first=*head,*rest=(*head)->next; 
    if(!rest) 
     return; 

    reverse(&rest); 
    first->next->next = first; 
    first->next= NULL; 
    *head = rest;                
    // printf(" :%d",rest->data); 
} 

此程序正在工作。所提到的遞歸代碼是用於反轉單鏈表的。考慮列表L = {1,2,3,4,5}作爲輸入。考慮兩種情況，情況1，如果我們取消註釋語句10，輸出將是最後一個節點的數據即5次四次，案例2如果我們評論陳述號。 09然後printf將打印5,4,3,2。我的問題是，在這種情況下1由於這種說法*頭=休息;爲什麼我們爲每個函數調用獲得不變的值 - >數據？如果我們刪除了聲明號。 09然後printf將打印rest-> data的不同值。
非常感謝你提前。

Answer 1

這裏就是答案！ :-)

void reverse(LIST **head) 

{  

    01: if(!*head) 
    02:  return ; 

    03: LIST *first=*head,*rest=(*head)->next; 
    04: if(!rest) 
    05:  return; 
    06: reverse(&rest); //head pointer in new function call context is a rest pointer in previous function call context. 

    07: first->next->next = first; 
    08: first->next= NULL; 
    09: *head = rest; 


    10: // printf(" :%d",rest->data); 
} 

這裏發生的事情是每次函數調用返回， 「*頭=休息;」這個語句正在使用靜態指針的地址更新位於頭部（這是頭指針的地址）的值，這在整個程序執行上下文中都有效。每次函數調用返回頭指針被更新時，意味着每個先前的調用休息指針被更新（參見第6行註釋）。

Answer 2

您沒有將first連接到返回列表的尾部（rest）。一個簡單的方法是使用一個數組來存儲所有元素，並以相反的順序迭代數組 - 就像一個堆棧。

另一個選擇，使用遞歸是從reverse返回'尾'。一旦你有尾巴，首先連接它並返​​回它很簡單（因爲first是新的尾巴）。

這裏的工作代碼使用遞歸：

typedef struct LIST { 
    int   data; 
    struct LIST *next; 
} LIST; 

LIST* reverse(LIST **head) 
{ 
    LIST *first, *rest, *tail; 
    if (!*head) return NULL; 

    first = *head; 
    rest = first->next; 

    if (!rest) return first; // new tail 

    tail = reverse(&rest); 
    tail->next = first; 
    first->next = NULL; 

    *head = rest;                
    return first; // new tail 
    // printf(" :%d",rest->data); 
} 

int main(void) { 
    LIST list[5] = { {1, 0}, {2, 0}, {3, 0}, {4, 0}, {5, 0}}; 
    LIST *head = list; 
    int i = 0; 
    for (; i < 4; ++i) { 
     list[i].next = &list[i+1]; 
    } 
    reverse(&head); 
    return 0; 
}