我在理解以下代码块时遇到了一些问题：
void InsertSorted(Entry * & list, Entry * newOne) {
if (list == NULL || newOne->name < list->name) {
newOne->next = list;
list = newOne;
} else {
InsertSorted(list->next, newOne);
}
}
我尝试跟踪代码，但只能到达第一个 if 语句。一旦我到了执行第一个 if 语句的地步，我不明白以前对 InsertSort 的调用如何设法将列表的前半部分连接到新创建的列表。
谢谢
要理解这个函数，只需绘制每次调用时获得的数据。
假设你有一个这样的列表(假设名称是一个int(：
1 -> 4 -> 6 -> 7 -> 10 -> NULL
你想插入5.
在第一次调用时，list通过原始调用方指针引用1。也就是说，如果您这样做：
InsertSorted(myList, someNode);
函数内部的list是指函数外部的myList，在函数内部更改它会在外部更改它。现在，不会传递 if 条件，因为list不是NULL，newOne->name不是< list->name。所以函数调用自己，用list的next指针和newOne。这就是我们现在所处的位置：
1 -> 4 -> 6 -> 7 -> 10 -> NULL
^ list refers to this one
5
^ this is newOne, floating off somewhere by itself
在下一个调用中，list是指上次调用的list->next，这意味着它指的是 4 .同样，if不满意，所以我们继续else：用list->next再次调用函数(记住list现在指的是4，这使得list->next引用此调用中的6(。这就是我们现在所处的位置：
1 -> 4 -> 6 -> 7 -> 10 -> NULL
^ list refers to this one through 1's next pointer
5
^ this is newOne, floating off somewhere by itself
在下一个调用中，list指的是4的next指针，它表示6。列表如下所示：
1 -> 4 -> 6 -> 7 -> 10 -> NULL
^ list refers to this one through 4's next pointer
5
^ this is newOne, floating off somewhere by itself
这一次，if满意(因为5<6(，所以我们
newOne->next指向list。这使得表示5的新节点指向6，因为它next节点。将"
list"设置为newNode。这可能令人困惑，但请记住，list是一个参考，这意味着更改它会更改原始内容。当list引用4时，原版是list->next的，所以它与将指向4的next指针的节点设置为指向newOne相同。
这意味着列表现在如下所示：
1 -> 4 -> 5 -> 6 -> 7 -> 10 -> NULL
^ here's newOne
并且该函数不执行任何调用，因此该函数终止，控制权返回到最初调用它的函数。
您刚刚按排序顺序插入了新元素。
您需要考虑三种极端情况：
- 列表为空(立即
list == NULL( - 要插入的元素小于所有现有元素
- 要插入的元素大于所有现有元素
假设您总是尝试插入5作为这些测试的新元素。
所以对于第一个，当list为 NULL 时 - 也就是说，您的列表看起来像
NULL
if语句将立即为 true，您将newOne->next设置为 list(这意味着newOne->next NULL(，list设置为 newOne 。该函数退出，您的列表如下所示：
5 -> NULL
目前为止，一切都好。
如果您要插入的元素小于所有其他元素，请像这样说：
7 -> 9 -> NULL
5
^ newOne
然后if也会立即触发。您将newOne->next设置为 list ，这使它指向7，并将list设置为 newOne 。
5 -> 7 -> 9 -> NULL
这是处理的。
最后一个极端情况是新元素大于所有现有元素。假设你有
3 -> NULL
作为您的列表。在第一次传递时，list将指向 3，并且不会触发if。因此，您将使用指向NULL的list->next调用该函数。触发if(因为list == NULL(，您将newOne->next设置为list(这是NULL(，然后将list设置为newOne，这使3->next指向newOne，因为在第一次调用中，您通过引用传递了其next指针，这意味着更改list更改它。现在您有：
3 -> 5 -> NULL
这都很好。因此，此函数似乎可以为任何列表生成所需的结果。
作为旁注，这个函数是尾递归的，但可以通过使其迭代而不是递归来加快速度。不过，这是一个很好的学习练习。
另请注意，这不是插入排序，因为您不是采用未排序的列表并对其进行排序，而只是以类似于插入排序的方式在现有列表中插入新数据。
这是插入排序，该项目将根据顺序插入到其放置的列表中。一旦您到达列表的末尾，或者在列表中找到项目应所在的位置，递归就会结束。
请注意，对于您在列表中前进的每条递归调用，列表指针的"头"基本上会在列表中移动。
基本上，如果这是它的正确位置，此代码会在列表的开头插入新元素 - 否则，它会向下移动并将下一个元素视为"开始"。
关键是列表指针是通过引用传递的，所以当我们说"list = newOne;"时，它实际上在调用者的作用域中起作用。因此，当我们调用"InsertSorted(list->next， newOne("时，它实际上可以更新我们的列表。
newOne->next = list;
将 newOne 列表节点的下一个字段设置为当前列表的前面。
list = newOne;
设置跟踪列表前面的指针(称为"列表"(以指向列表中新的第一个节点 newOne。
上述情况仅在列表为空的情况下发生。else 条件沿列表向下移动一个节点，直到它找到列表中的最后一个节点，由 if 语句条件控制。
由于参数是通过引用传递的(如"&"字段所示(，因此在函数内部所做的更改会保留在程序中的所有位置。
我不明白以前对 InsertSort 的调用如何设法将列表的前半部分连接到新创建的列表。
"列表的前部"已经与自身完全连接 - 这就是使它成为列表的原因。
算法为：
1( 找到插入点。2( 将新条目连接到位。现在一切都连接起来了。
我们通过递归找到当前列表的末尾：如果我们在那里，那么我们就在那里;否则，我们检查下一个链接。我们以相同的方式"检查下一个链接"，所以如果这是结束，那么我们就完成了，否则我们继续下一个链接，依此类推。
当我们到达最后时，我们执行以下步骤：
newOne->next = list;
list = newOne;
这意味着：
1(告诉新条目链接到列表的尾部。2(告诉列表的头部链接到新条目。
这是有效的list因为它是对指针的引用。
newOne->next = list将指针值从list复制到newOne->next 中。这意味着newOne指向的Entry现在有一个指向list指向同一位置的next字段，即列表中的下一个元素。因此，我们已将新条目链接到列表的尾部。
list = newOne将指针值从newOne复制到list 中。这意味着指针本身list - 它是列表头部最后一个Entry的一部分 - 现在指向newOne指向的示例位置 - 即新Entry。因此，我们已将列表的头部链接到新条目。
由于引用，list是列表中Entry节点一部分的实际指针，而不仅仅是碰巧指向同一位置的随机Entry*局部变量。