反向單鏈表的遞歸方法？

Question

我在

http://www.geeksforgeeks.org/write-a-function-to-reverse-the-nodes-of-a-linked-list/

看到這個遞歸程序（C語言）扭轉單向鏈表。

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

在此步驟中該程序，

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

我可以寫 「休息 - >下一=第一;」 代替 「一線>下一步 - >下一=第一;」？

或者是否有寫「first-> next-> next = first;」的意義？

Answer 1

那麼，當你嘗試這種變化時發生了什麼？ 當然你可以寫它......但語義可能會改變。

將first->next指定爲rest並不強制它們始終保持一致。您的緊前面的聲明將指針傳遞給rest轉換爲recursiveReverse。總之，你預計rest改變。

rest現在應該指向其餘列表的頭部。這不再是first->next;現在應該是反向列表的結束，其中rest是該列表的頭部。

這是否足以說明問題？如果沒有，請填寫一些印刷說明來說明您的程序在每種情況下的作用。