C++完整代码：合并两个有序链表 |21xrx.com

C++完整代码：合并两个有序链表

2023-07-11 17:32:43 深夜i -- --

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) {
    // 建立虚拟头节点dummy，pre指针指向它
    ListNode* dummy = new ListNode(0);
    ListNode* pre = dummy;
    // 遍历链表l1和l2，按顺序比较节点val大小，将小的节点接到pre后面
    while (l1 && l2) {
      if (l1->val <= l2->val)
        pre->next = l1;
        l1 = l1->next;
       else
        pre->next = l2;
        l2 = l2->next;
      
      pre = pre->next;
    }
    // l1或l2为空，直接将非空的链表连接到pre后面即可
    if (l1)
      pre->next = l1;
     else
      pre->next = l2;
    
    // 返回dummy->next即为新链表头节点
    return dummy->next;
  }
};
int main()
{
  Solution s;
  // 创建两个有序链表
  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* res = s.mergeTwoLists(l1, l2);
  // 打印新的有序链表
  while (res)
    cout << res->val << " ";
    res = res->next;
  
  return 0;
}

在这段程序中，我们首先定义了一个ListNode的结构体，它表示链表的一个节点，其中val表示节点的数据，next表示指向下一个节点的指针。

我们在程序中定义了一个Solution类，其中包含mergeTwoLists函数，该函数接收两个有序链表l1和l2作为参数，将它们合并成一个新的有序链表，并返回新链表的头节点。

在mergeTwoLists函数中，我们首先创建了一个虚拟头节点dummy，并将pre指针指向它。接着，我们遍历链表l1和l2，按顺序比较节点val大小，将小的节点接到pre后面。最后，我们判断l1和l2是否为空，若不为空，则将非空的链表连接到pre后面即可。最后，我们返回头节点dummy->next即为新链表的头节点。

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

下一篇: 《C++程序设计第四版PDF》

评论区

()

相似文章