对插入链表感到困惑

Question

这是节点类本身的代码：

struct Node {
int data;
struct Node * next;
Node(int x) {
data = x;
next = NULL;
}
};

下面的代码在链表的开头插入一个新节点。我的问题是为什么第四行没有打乱列表的顺序。如果head之前在new_node之后的位置，那么设置head等于new_node不会弄乱列表。当我运行代码时，它按预期工作，但我不知道为什么。

Node *insertAtBegining(Node *head, int newData) {
Node* new_node = new Node(newData);
new_node -> next = head;
head = new_node;
return head;
}

我的第二个问题是关于下面的代码，它应该在链表的末尾插入一个项目。我理解这个是如何工作的，我只是不明白为什么它的简化版本不起作用。

Node *insertAtEnd(Node *head, int newData)  {
Node* new_node = new Node(newData);
if(head == nullptr){
head = new_node;
return head;
}
else{
Node* trav = head;
while(trav -> next != nullptr){
trav = trav -> next;
}    
trav -> next = new_node;
return head;
}
}

简化版

Node *insertAtEnd(Node *head, int newData)  {
Node* new_node = new Node(newData);
Node* trav = head;
while(trav != nullptr){
trav = trav -> next;
}
trav = new_node;
}

简化版本仅将您尝试添加的最后一个节点附加到列表的末尾。因此，如果您尝试附加1、2和3，则只会添加3。既然trav指针变成了最后一个下一个指针，它不应该做同样的事情吗？

Answer 1

head不是节点。它是一个保存节点地址的变量。

head = new_node;不移动任何节点！它查看new_node变量(即节点的地址(中的值，并将相同的值存储到head变量中。它不会改变列表。它只更改head变量。

此行将更改新节点。它说，新节点之后的节点是head变量中当前地址为的节点。

new_node -> next = head;

请注意，我们还没有将新节点算作列表的一部分，因为您无法从第一个节点(地址在head变量中的节点(访问它。

此行：

head = new_node;

将CCD_ 8设置为新节点的地址现在我们可以说新节点在列表中，因为现在；第一节点"-地址在CCD_ 9变量中的那个是新的。不是因为更改了节点，而是因为更改了head变量。

---

注意，head是函数中的局部变量。如果你调用这个函数并且只执行CCD_ 12；改变列表"；因为您的head变量仍然指向以前的变量。函数中的变量已更改，但该变量不再使用。你必须做head = insertAtBeginning(head, 5)。

Answer 2

第一个代码：

您正在创建一个newnode，要在前面插入，您需要将next of newnode设置为current head，然后将newnode设置为head(并将其返回存储为当前头(

这正是第一个代码所要做的。所以这里没问题。

第二个代码(简化版(：

• 这里没有存储head(就像第一个代码一样，您返回了头并进行了适当的存储(
• 此外，您正在遍历，直到它变为null(您已经过了最后一个元素(，并创建newnode
• 您没有将newnode链接到链接列表的末尾

第二代码解决方案(简化版(

Node *insertAtEnd(Node *head, int newData)  {

Node* new_node = new Node(newData);
// if this is the first node (head will be NULL)
if (!head) {
return new_node; 
}
Node* trav = head;
while(trav->next != nullptr){
trav = trav -> next;
}
trav->next = new_node;
return head;
}

Answer 3

在insertAtEnd中，如果列表为空，则head将为null。如果head为null，则需要设置head。然后您可以返回新的头。

if(trav != nullptr) {do something}
else head = new_node;

现在它将更新头，但不会更新下一个值。您可以通过在最后一个值上停止并设置其"；下一个"；指向new_node指针的指针。

while(trav->next != nullptr){
trav = trav -> next;
}
trav->next = new_node;

所以最终结果看起来像这样：

Node *insertAtEnd(Node *head, int newData)  {
Node* new_node = new Node(newData);
Node* trav = head;
if(trav != nullptr) {
while(trav->next != nullptr) 
trav = trav -> next;
trav->next = new_node;
}else head = new_node;
return head;
}