鏈接列表：使用遞歸插入一個節點

Question

我在想，以下兩段代碼如何執行將新節點插入鏈接列表的相同工作？

verison1

version2

在版本1，有一個prev指針能夠卷繞前一節點至所述新節點。

但我在Version2中看不到它。在版本2中，以前的鏈接被破壞（即它沒有鏈接到新節點），我錯過了什麼嗎？

Answer 1

讓我們深入到你的版本2插入：

void RecInsertSorted(Entry*& list, Entry* newOne) { 
    if (list == nullptr || newOne->name < list->name) { 
     newOne->next = list; 
     list = newOne; 
    else { 
     RecInsertSorted(list->next, newOne); 
    } 
} 

你不需要prev工作以來，通過電話進行。這是爲什麼？因爲list參數是對指針的引用。

假設我們在第一個元素和第二個元素之間插入newOne。在最後你想你的名單看起來像：

部件1 - > newOne - > element2的

當條件newOne->name < list->name滿足，list指element2中。但是這是對指針的引用，引用指的是element1-> next！因此，當陳述list = newOne;運行時，它會相應地更新element1->next，並且您的列表格式良好。

類似地，當在末尾插入newOne時，list是nullptr。但是，再次，這是一個參考，所以newOne->next變成nullptr和newOne成爲列表的結尾。

同樣，如果必須在第一個元素之前插入newOne，它會更新一些指針，以便跟蹤列表的頭部......因此成爲列表中的第一個元素。