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

C++单链表合并实现

2023-07-01 19:51:59 深夜i 19 0

C++ 单链表合并实现

C++是一种高级编程语言，广泛应用于各种计算机科学领域。单链表合并是一项基础的数据结构操作，主要是将两个单链表合并成一个新的单链表。在C++中，实现单链表合并可以通过编写自定义的函数来完成。

首先，定义单链表的节点结构体，包含一个数据成员和一个指向下一个节点的指针：

struct ListNode{
  int val;
  ListNode* next;
  ListNode(int x) : val(x), next(NULL) {}
};

接下来，创建一个函数mergeTwoLists()，该函数输入两个单链表的指针，返回一个新的单链表的指针。

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
  ListNode* dummy = new ListNode(0);
  ListNode* tail = dummy;
  while (l1 && l2) {
    if (l1->val < l2->val)
      tail->next = l1;
      l1 = l1->next;
     else
      tail->next = l2;
      l2 = l2->next;
    
    tail = tail->next;
  }
  tail->next = (l1 ? l1 : l2);
  return dummy->next;
}

在函数中，首先声明一个虚拟头节点dummy和一个尾节点tail。同时对两个链表中的值进行比较，将较小的节点插入到新的链表中，并移动指针。最后，将剩余的节点链接到新的链表的尾部。

为了使用该函数，我们需要一个示例来测试，下面创建两个链表，并向它们中添加一些元素：

int main()
{
  ListNode* l1 = new ListNode(1);
  l1->next = new ListNode(2);
  l1->next->next = new ListNode(4);
  ListNode* l2 = new ListNode(1);
  l2->next = new ListNode(3);
  l2->next->next = new ListNode(4);
  ListNode* mergedList = mergeTwoLists(l1, l2);
  while(mergedList)
    cout << mergedList->val << " ";
    mergedList = mergedList->next;
  
  cout << endl;
  return 0;
}

该示例创建了两个有序的链表，并将它们输入到一个mergeTwoLists()函数中，输出结果为：

1 1 2 3 4 4

我们可以看到，返回的新链表已经按顺序排列，并成功将输入的两个链表合并为一个链表。

在C++中，使用单链表的方式有很多，单链表的合并是其常见的操作之一。通过编写自定义函数，可以轻松实现单链表的合并，提高程序的效率和可读性。

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

下一篇: 使用C++的pen如何绘制圆形？

评论区

相似文章