鏈表遞歸反向

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; 

    /* put the first element on the end of the list */ 
    recursiveReverse(&rest); 
    first->next->next = first; 

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

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

我不明白的是在例如，最近的遞歸步驟，如果列表是1-2-3-4現在對於最後一個遞歸步驟，首先是1，其餘的將是2.所以，如果你設置* head_ref = rest ..這使得列表2的頭部？有人可以解釋如何在逆轉名單的頭後成爲4？

Answer 1

其餘不是2，它是2 -> 3 -> 4，它遞歸地逆轉。 之後，我們將*head_ref設置爲rest，現在（遞歸顛倒！）4 -> 3 -> 2。

重要這裏的一點是，儘管兩個first和rest具有相同的類型，即node*，它們在概念上根本不同：first點一個單一元素，而rest指向連接的元素列表。這個鏈表在它被分配到*head_ref之前被遞歸地逆轉。

Answer 2

拉出一個堆棧跟蹤...

Intial - {1,2,3,4} 
Head - 1 
Rest = 2,3,4 
Recurse(2,3,4) 
Head = 2 
Rest = 3,4 
Recurse(3,4) 
Head = 3 
Rest = 4 
Recurse (4) 
Head = 4 
Rest = null //Base Case Reached!! Unwind. 

So now we pick up 
Recurse(3,4) 
Head = 3 
Rest = 4 
// Return picks up here 
first->next->next = first; 
so list is: 
3,4,3 
// set head to null, 
null ,4,3, 
//Off with his head! 
4,3 
Return 

Now we're here 
Recurse(2,3,4) 
Head = 2 
Rest = 3,4 
Previous return leaves state as: 
Head = 2 //But Head -> next is still 3! -- We haven't changed that yet.. 
Rest = 4,3 
Head->next is 3, 
Head->next->next = 2 makes the list (actually a tree now) 
4->3->2 
^
    | 
    2 
And chop off the head leaving 
4->3->2 
and return. 

Similarly, do the last step which will leave 
4->3->2->1 
    ^
     | 
     1 
and chop off the head, which removes the one. 

Answer 3

考慮名單：

1 -> 2 -> 3 -> 4 -> NULL 
^ ^
    |  | 
first rest 

凡first點到第一節點和休息點到節點旁邊first。

由於列表不是空的且列表不包含一個節點，因此我們對reverse進行遞歸調用以反轉rest指向的列表。這是列表看起來如何扭轉列表的其餘部分之後：

1 -> 2 <- 3 <- 4 
^ |   ^
    |  NULL   | 
first     rest 

可以看出rest現在指向具有4在開始和2在列表的最後的逆轉列表。節點2的下一個指針是NULL。

現在我們需要將第一個節點追加到反向清單列表的末尾。要追加任何東西到列表的最後，我們需要訪問列表的最後一個節點。在這種情況下，我們需要訪問倒排列表的最後一個節點。看圖first -> next指向最後一個節點的反向休息列表。因此first -> next -> next將成爲倒排列表的最後一個節點的下一個指針。現在，我們需要讓它指向first所以我們做：

first -> next -> next = first; 

這一步後的名單看起來像：

1 <- 2 <- 3 <- 4 
^->    ^
    |     | 
first     rest 

現在列表中的最後一個節點的next字段必須NULL。但現在情況並非如此。最後一個節點（節點1）的next字段指向其之前的節點（節點2）。爲了解決這個問題，我們做的事：

first -> next = NULL; 

在此之後，列表如下所示：

NULL <- 1 <- 2 <- 3 <- 4 
     ^    ^
     |     | 
     first     rest 

所看到的列表現在正確地rest指向反轉的列表的頭部反轉。

我們需要返回新的頭指針，以便這些更改反映在調用函數中。但是，這是一個void功能和head作爲雙指針傳遞，因此改變*head值會使調用函數查看更改頭：

*head = rest; 

Answer 4

我最近寫了一個遞歸方法用於逆轉紅寶石鏈表。這裏是：

def reverse!(node_1 = @head, node_2 = @head.link) 
    unless node_2.link 
     node_2.link = node_1 
     @head = node_2 
     return node_1 
    else 
     return_node = reverse!(node_1.link, node_2.link) 
     return_node.link = node_1 
     node_1.link = nil 
     return node_1 
    end 
    return self 
end