合并2个链表并追加到链表c++的末尾

Question

到目前为止，我知道的还不多，但我正在尝试掌握使用链表的诀窍。

结构：

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

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

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为节点。

编辑:在我的main中，我像这样调用addNode函数：

Node *head = new Node;

insertAtEnd(head,20);

这是正确的吗，或者这可能是异常的原因？

Answer 1

用下面的方法声明函数

void addNode( Node* &head, int x) ;

而不是下面的代码片段

Node *head = new Node;

insertAtEnd(head,20);

您必须在第一次调用该函数时使用以下方法

Node *head = nullptr; // or NULL

addNode(head,20);

请注意，在您的帖子中没有名为insertAtEnd的函数。有函数addNode。：)

如果您需要合并两个列表，那么您可以使用此演示程序作为示例。当然，您还需要添加一些其他功能，例如删除列表以获得完整的项目。

#include <iostream>

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

Node * insert( Node *current, int value )
{
    Node *tmp;

    if ( current == nullptr )
    {
        tmp = new Node { value, nullptr };
    }
    else
    {
        tmp = new Node { value, current->next };
        current->next = tmp;
    }

    return tmp;
}

std::ostream & display( Node *head, 
                        std::ostream &os = std::cout,
                        const char *delimiter = " " )
{
    for ( ; head; head = head->next ) os << head->value << delimiter;

    return os;
}

Node * merge( Node * &head1, Node * &head2 )
{
    Node *new_head = nullptr;
    Node *current  = nullptr; 

    while ( head1 != nullptr && head2 != nullptr )
    {
        Node *tmp;
        if ( head2->value < head1->value )
        {
            tmp = head2;
            head2 = head2->next;
        }
        else
        {
            tmp = head1;
            head1 = head1->next;
        }

        tmp->next = nullptr;
        if ( new_head == nullptr )
        {
            new_head = tmp;
            current = new_head;
        }
        else
        {
            current->next = tmp;
            current = current->next;
        }
    }

    if ( head1 != nullptr ) new_head == nullptr ? new_head : current->next = head1;
    if ( head2 != nullptr ) new_head == nullptr ? new_head : current->next = head2;


    head2 = nullptr;
    head1 = new_head;

    return new_head;
}

int main() 
{
    Node *list1 = nullptr;
    Node *list2 = nullptr;

    list1 = insert( list1, 4 );
    insert( insert( list1, 10 ), 20 );

    display( list1, std::cout << "List1: " ) << std::endl;

    list2 = insert( list2, 2 );
    insert( insert( insert( list2, 5 ), 15 ), 60 );

    display( list2, std::cout << "List2: " ) << std::endl;

    std::cout << std::endl;

    merge( list1, list2 );

    display( list1, std::cout << "List1: " ) << std::endl;
    display( list2, std::cout << "List2: " ) << std::endl;

    return 0;
}

程序输出为

List1: 4 10 20 
List2: 2 5 15 60 

List1: 2 4 5 10 15 20 60 
List2: 

Answer 2

通过这样做：

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);

除了now--一个完全不同的命名函数，你的节点是默认初始化的。在您的例子中，这意味着从new Node;得到的Node对于value和next都有不确定的值。然后将其传递给函数，该函数假定一个确定值(null)来终止循环。

这可以通过许多方式来解决；上面代码的机制就是这样一种方式。如果列表管理代码理解NULL意味着无列表，则不需要首先预分配头节点。你在addNode上最初的帖子似乎--至少--试着遵循这句咒语。

Answer 3

这可能是异常的原因：

struct Node 
{
   int value;     <-----  Node structure has value property
   Node *next;
};


Node* temp = new Node;
temp->data = x;   <------ Assigning to data property of Node which does not exists
temp->next = NULL;

要添加列表，您可以使用相同的方法

void addNode(Node* head, Node* head2) 
{

  Node* last = head;
  while(last->next) last=last->next;

  last->next = head2;
}