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

C++实现合并有序链表

2023-06-26 16:14:41 深夜i -- --

C++ 合并有序链表实现数据结构

链表是一种重要的数据结构，常用于实现各种算法。在本文中，我们将介绍如何使用C++语言来实现合并有序链表。

有序链表定义为按照升序排列的链表。合并有序链表指的是将两个有序链表合并成一个新的有序链表。具体来说，我们需要将原始链表中的每个节点按照升序排列，然后重新构建一个新的链表。

下面是使用C++语言实现合并有序链表的一般步骤：

1. 创建一个新的链表

2. 遍历两个有序链表

3. 选择一个值较小的节点，并将其添加到新的链表中

4. 继续遍历剩余的节点，直到两个链表中的所有节点全部处理完成。

5. 返回新链表

具体实现过程如下：

 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* dummy = new ListNode(-1); // 创建一个哑节点
  ListNode* cur = dummy; // 当前节点指向哑节点
  while (l1 != NULL && l2 != NULL) {
    if (l1->val < l2->val) // 比较两个链表当前节点的大小 else
      cur->next = l2;
      l2 = l2->next;
    
    cur = cur->next;
  }
  // 将未处理完的链表剩余部分拼接到新链表中
  if (l1 != NULL)
    cur->next = l1;
   else
    cur->next = l2;
  
  return dummy->next;
}
int main() {
  ListNode* l1 = new ListNode(1);
  l1->next = new ListNode(3);
  l1->next->next = new ListNode(5);
  ListNode* l2 = new ListNode(2);
  l2->next = new ListNode(4);
  l2->next->next = new ListNode(6);
  ListNode* mergeList = mergeTwoLists(l1, l2);
  ListNode* cur = mergeList;
  while (cur != NULL)
    cout << cur->val << " ";
    cur = cur->next;
  
  cout << endl;
  return 0;
}

在上面的代码中，我们首先创建了一个哑节点，并将当前节点指向哑节点。然后，我们遍历每个链表，并根据每个节点的大小将其添加到新链表中。最后根据未处理完的链表剩余部分，将其拼接到新链表中。

执行上述代码，输出结果如下：

1 2 3 4 5 6

我们可以看到，合并后的链表已经按照升序排列了。

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

下一篇: C++中实现字符串中标点替换

评论区

()

相似文章