C++实现链表合并 |21xrx.com

C++实现链表合并

2023-06-27 16:49:22 深夜i -- --

C++ 链表合并

链表是一种数据结构，它由多个节点串联而成，每个节点包含一个数据元素和指向下一个节点的指针。链表合并是指将两个链表合并成一个新的链表。在C++语言中，链表可以通过指针来实现，指针可以指向链表的头节点，并通过遍历链表来访问节点。

链表合并的实现可以分为以下几个步骤：

1. 创建新的链表头节点，用一个指针指向它。

2. 遍历第一个链表，将其中的每个节点都插入到新链表中。

3. 遍历第二个链表，将其中的每个节点都插入到新链表中。

4. 返回新链表的头节点。

下面是一个C++实现链表合并的示例代码：


#include<iostream>
using namespace std;
struct Node {
  int data;
  Node* next;
};
Node* mergeLists(Node* head1, Node* head2) {
  //创建新的链表头节点
  Node* dummyHead = new Node;
  Node* curr = dummyHead; //指针指向新链表头节点
  //遍历链表1，将节点插入到新链表中
  while(head1 != NULL)
    curr->next = new Node;
    curr = curr->next;
    curr->data = head1->data;
    curr->next = NULL;
    head1 = head1->next;
  
  //遍历链表2，将节点插入到新链表中
  while(head2 != NULL)
    curr->next = new Node;
    curr = curr->next;
    curr->data = head2->data;
    curr->next = NULL;
    head2 = head2->next;
  
  //返回新链表的头节点
  Node* newHead = dummyHead->next;
  delete dummyHead;
  return newHead;
}
int main() {
  Node* head1 = new Node;
  head1->data = 1;
  head1->next = new Node;
  head1->next->data = 2;
  head1->next->next = new Node;
  head1->next->next->data = 4;
  head1->next->next->next = NULL;
  Node* head2 = new Node;
  head2->data = 1;
  head2->next = new Node;
  head2->next->data = 3;
  head2->next->next = new Node;
  head2->next->next->data = 4;
  head2->next->next->next = NULL;
  Node* head = mergeLists(head1, head2);
  while(head != NULL)
    cout<<head->data<<" ";
    head = head->next;
  
  cout<<"\n";
  return 0;
}

在这个示例代码中，我们定义了一个结构体Node，表示节点，它包含两个成员变量，一个是int类型的数据data，另一个是指向下一个节点的指针next。我们还定义了一个函数mergeLists，接受两个链表的头节点作为参数，并返回新链表的头节点。

在函数mergeLists中，我们首先创建了新链表的头节点dummyHead，并用指针curr指向它。然后，我们遍历链表1，将其中的每个节点都插入到新链表中。具体地，我们用new运算符创建一个新的节点，并将curr的next指针指向它，然后将curr指针指向新节点，并将新节点的data成员变量设置为head1节点的data成员变量。最后，我们将head1指针指向下一个节点，继续遍历链表1。

接下来，我们遍历链表2，将其中的每个节点都插入到新链表中。同样地，我们用new运算符创建一个新的节点，并将curr的next指针指向它，然后将curr指针指向新节点，并将新节点的data成员变量设置为head2节点的data成员变量。最后，我们将head2指针指向下一个节点，继续遍历链表2。

最后，我们返回新链表的头节点，并释放dummyHead节点的内存。在主函数中，我们创建了两个链表，然后调用mergeLists函数将它们合并，最后遍历新链表并打印它的每个节点的数据。在这个示例代码中，新链表的输出应该是1 2 4 1 3 4。

上一篇: idea打包java可执行jar包

下一篇: C++编译器未安装

评论区

()

相似文章