C++合并两个有序链表 |21xrx.com

C++合并两个有序链表

2023-07-04 21:47:34 深夜i -- --

C++ 合并有序链表算法指针

C++是一种高级编程语言，广泛应用于软件开发。而链表是一种数据结构，常被用于存储和操作数据。该文章将介绍C++如何合并两个有序链表。

有序链表是指每个节点按照一定的顺序排列，比如数字从小到大。合并两个有序链表，可以先创建一个新的链表，然后遍历原链表，取出节点按照一定的顺序插入到新链表中。

下面是一个示例代码，该代码使用了C++的类和结构体，同时使用指针操作链表：


#include <iostream>
using namespace std;
// 链表节点结构体
struct ListNode {
  int val;
  ListNode *next;
  ListNode(int x) : val(x), next(NULL) {}
};
class Solution {
public:
  ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    ListNode dummy(0); // 新链表的虚拟头节点
    ListNode* tail = &dummy; // 新链表的尾节点
    while (l1 && l2) {
      if (l1->val <= l2->val) // 将l1的节点插入新链表
        tail->next = l1;
        l1 = l1->next;
       else // 将l2的节点插入新链表
        tail->next = l2;
        l2 = l2->next;
      
      tail = tail->next; // 更新尾结点
    }
    if (l1) // l1还有节点未插入
    if (l2) 直接将剩余节点插入新链表
      tail->next = l2;
    
    return dummy.next; // 返回新链表的头节点
  }
};
int main() {
  // 创建链表1: 1 -> 3 -> 5
  ListNode l1_1(1), l1_2(3), l1_3(5);
  l1_1.next = &l1_2;
  l1_2.next = &l1_3;
  // 创建链表2: 2 -> 4 -> 6
  ListNode l2_1(2), l2_2(4), l2_3(6);
  l2_1.next = &l2_2;
  l2_2.next = &l2_3;
  // 创建解决方案对象并调用合并方法
  Solution s;
  ListNode* res = s.mergeTwoLists(&l1_1, &l2_1);
  // 输出结果
  while (res)
    cout << res->val << " ";
    res = res->next;
  
  cout << endl;
  return 0;
}

该代码中，有序链表的每个节点被封装在`ListNode`结构体中。`val`表示节点的值，`next`指向下一个节点。`Solution`类通过`mergeTwoLists`方法实现了两个有序链表的合并。

当然，该代码还有一些可以改进的地方。比如可以在链表头插入虚拟头节点，简化节点插入的逻辑等。不过，该代码应该足以解决大部分有序链表合并的问题了。

总之，使用C++合并两个有序链表，需要注意链表的节点顺序和空指针的处理。通过上述示例代码的学习和理解，可以帮助读者更好地掌握链表的基本操作和C++的编程技巧。

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

下一篇: VC++ 2015安装失败：可能的原因和解决方法

评论区

()

相似文章