链接列表：使用递归插入一个节点

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，它会更新一些指针，以便跟踪列表的头部......因此成为列表中的第一个元素。