C++单链表合并的实现方法 |21xrx.com

C++单链表合并的实现方法

2023-07-03 07:33:33 深夜i 14 0

C++ 单链表合并实现方法

单链表是一种基本的数据结构，为了更好地利用单链表，有时需要把两个单链表合并成一个链表。这种操作在实际中非常常见。在C++中，单链表合并也是一种常见的操作，下面介绍一下C++单链表合并的实现方法。

C++中单链表通常是通过指针来实现的，因此在合并两个单链表时，需要对它们的指针进行操作。具体步骤如下：

1. 创建两个单链表ListA和ListB，假设它们分别包含m个元素和n个元素。

2. 定义一个新的单链表ListC，用于存放合并后的结果。

3. 从ListA和ListB中依次取出节点，比较它们的值的大小，并将较小的节点插入到ListC中。

4. 如果有一个链表已经到达了末尾，则将另一个链表中剩余的节点依次插入到ListC中。

5. 最后返回ListC，即为合并后的结果。

下面是C++代码的实现：

#include<iostream>
using namespace std;
struct ListNode {
  int val;
  ListNode *next;
  ListNode(int x) : val(x), next(NULL) {}
};
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
  ListNode *head, *tail;
  head = tail = new ListNode(0);
  while (l1 && l2) {
    if (l1->val < l2->val)
      tail->next = l1;
      l1 = l1->next;
     else
      tail->next = l2;
      l2 = l2->next;
    
    tail = tail->next;
  }
  if (l1) tail->next = l1;
  if (l2) tail->next = l2;
  return head->next;
}
int main() {
  ListNode *l1 = new ListNode(1);
  ListNode *l1_1 = new ListNode(3);
  ListNode *l1_2 = new ListNode(5);
  l1->next = l1_1;
  l1_1->next = l1_2;
  
  ListNode *l2 = new ListNode(2);
  ListNode *l2_1 = new ListNode(4);
  ListNode *l2_2 = new ListNode(6);
  l2->next = l2_1;
  l2_1->next = l2_2;
  ListNode *l3 = mergeTwoLists(l1, l2);
  while (l3)
    cout << l3->val << " ";
    l3 = l3->next;
  
  return 0;
}

上述代码中，ListNode结构体用于封装每个节点的值和指针。mergeTwoLists函数用于合并两个链表，返回合并后的链表。在函数内部，定义了一个头节点和尾节点，用于构建新的链表。while循环中比较l1和l2的值的大小，依次插入到新链表中。最后，将剩余的节点插入到新链表中，并返回头节点的next，这样就得到了合并后的链表。

总之，C++单链表的合并是比较常见的操作，关键是要熟练掌握指针的相关知识。通过上述实现方法，能够方便地将两个单链表合并成一个链表，方便后续的处理。

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

下一篇: Java和Python：哪个更相似？

评论区

相似文章