c++ - 合并 2 个链表并附加到链表的末尾 C++

Question

到目前为止我还没有太多，但我正在尝试掌握使用链表的窍门。

结构:

struct Node 
{
   int value;
   Node *next;
};

如何将节点添加到列表的末尾？我只是想接受一个指向列表头部的指针和一个 int 值作为新节点添加。当我尝试运行我目前拥有的东西时，我得到了一个异常(exception)。

void addNode(Node* head, int x) 
{

    Node* temp = new Node;
    temp->data = x;
    temp->next = NULL;

     if(!head) 
     { 
         head = temp;
         return;
     } 
     else 
     {
         Node* last = head;
         while(last->next) 
         last=last->next;

         last->next = temp;
     }
}

我还没有真正开始合并这两个列表。我只知道我需要接收 2 个链表(或指向 2 个链表头部的指针？)，然后遍历所有节点的列表。

例如:链表 1 有 3 个节点:4、10、20。链表 2 有 4 个节点:2、5、15、60。

合并列表函数将生成一个新的链表，节点为 2,4,5,10,15,20,60。

编辑:在我的主程序中，我像这样调用 addNode 函数:

Node *head = new Node;

insertAtEnd(head,20);

这是正确的还是这可能是异常的原因？

Answer 1

这样做:

void addNode(Node* head, int x) 
// here ---------^

然后是:

 head = temp; // here

您只是修改了本地 head 指针，它采用从调用者传递的地址值。由于 head 不是对指针的实际引用(它只是一个指针)，结果是作为 head 传递的调用者指针保持不变。你永远不会将你分配的节点附加到你的列表中，泄漏内存，这将成为一个悲伤的日子......

改为通过引用传递指针。解决这个问题，然后修复无效的 data 成员，它实际上应该是 value 和一个指向指针的指针，用于遍历列表以找到结尾，结果可能看起来像像这样:

#include <iostream>

struct Node
{
    int value;
    Node *next;
};

void addNode(Node*& head, int x)
{
    Node **pp = &head;
    while (*pp)
        pp = &(*pp)->next;
    *pp = new Node;
    (*pp)->value = x;
    (*pp)->next = nullptr;
}

void printList(const Node *head)
{
    for (; head; head = head->next)
        std::cout << head->value << ' ';
    std::cout << '\n';
}

void freeList(Node *&head)
{
    while (head)
    {
        Node *p = head;
        head = p->next;
        delete p;
    }
}

int main()
{
    Node *head = nullptr;

    for (int i=1; i<=5; ++i)
        addNode(head, i);

    printList(head);
    freeList(head);
}

输出

1 2 3 4 5 

我将实现实际合并的任务留给您，但这应该足以让您启动并运行一个可管理的列表。

---

更新:来自 OP 的编辑问题:

Node *head = new Node;

insertAtEnd(head,20);

除了现在是一个完全不同的命名函数之外，您的节点是默认初始化的。在您的情况下，这意味着来自 new Node; 的结果 Node 具有 indeterminate 值 both value 和下一步。然后您将其传递给您的函数，该函数假定一个确定值(null)来终止您的循环。

这可以通过多种方式解决；上面代码的机制就是这样一种方式。如果列表管理代码理解为 NULL 表示无列表，则无需首先预分配头节点。您的 addNode 原始帖子似乎至少尝试遵循该口头禅。