合并2个链接列表并追加到链接列表的末尾C++

到目前为止，我还没有太多工作，但我正在尝试使用链接列表。合并2个链接列表并追加到链接列表的末尾C++

结构：

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个链表的头部的指针？），然后遍历所有节点的列表。

EG：链表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);

那是正确的或会是异常的原因是什么？

来源

2015-05-29 Bobo Amitheson

我会通过引用传递头指针开始。 'Node *＆head'。否则，你只是将指针值传递给这个函数，'head = ...'对调用者没有任何意义。 – WhozCraig

这里有一些一般的技巧（当然在你的课程材料中已经提到过）：1）将一个节点添加到单个链表的后面比将它添加到前面要慢得多。 2）通过维护一个迭代器（一个指针应该足够）到最后一个节点，你可以避免这种缓慢。这也避免了在合并时通过任一列表运行。 – user2079303

@Bobo Amitheson你如何合并列表？您是否必须创建一个新的第三个列表，或者是否需要将第二个列表中的所有节点移至第一个列表？ –

声明功能通过以下方式和

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:

来源

2015-05-29 07:14:17

这可能是例外的原因：

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

来源

2015-05-29 07:14:42 skazska

这应该会导致编译器错误，而不是一个例外。 – zahirdhada

当然是因为，为什么要编译它？ – skazska

@skazska你为什么要告诉我们skazski？:) –

这样做这个：

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具有为都value和next不确定值。然后你将它传递给你的函数，该函数假定一个确定的值（null）来终止你的循环。

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

来源

2015-05-29 07:24:46 WhozCraig

编辑：在我的主，我打电话的ADDNODE功能，像这样：

Node *head = new Node; 
insertAtEnd(head,20);

这是不对的。您没有初始化head->next，因此在insertAtEnd中，代码while(last->next) last=last->next;将尝试比较未初始化的指针，如果它不为null，则将对其进行取消引用。这可能会导致程序崩溃，而不是抛出异常。然后再次，它是未定义的行为，所以可能发生任何事情。

由于您插入功能已经涵盖插入到空单的情况下，我会简单地调用

head = nullptr; 
insertAtEnd(head,20)`;

除此之外，还有永不更新的功能外head指针，它已经被覆盖的bug在其他答案。

来源

2015-05-29 07:44:33 user2079303

合并2个链接列表并追加到链接列表的末尾C++

回答

相关问题