21xrx.com
2025-03-29 21:15:12 Saturday
文章检索 我的文章 写文章
C++合并两个有序链表的序列
2023-07-13 18:57:43 深夜i     14     0
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) {
    if (l1 == NULL) return l2;
    if (l2 == NULL) return l1;
    
    ListNode* head = new ListNode(0);
    ListNode* p = head;
    
    while (l1 != NULL && l2 != NULL) {
      if (l1->val < l2->val)
        p->next = l1;
        l1 = l1->next;
       else
        p->next = l2;
        l2 = l2->next;
      
      p = p->next;
    }
    
    if (l1 != NULL)
      p->next = l1;
     else if (l2 != NULL)
      p->next = l2;
    
    
    return head->next;
  }
};
int main() {
  Solution solution;
  
  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* result = solution.mergeTwoLists(l1, l2);
  
  cout << "[";
  while (result != NULL) {
    cout << result->val;
    result = result->next;
    if (result != NULL) ";
    
  }
  cout << "]" << endl;
  
  return 0;
}

在这个程序中，我们定义了一个Solution类来实现合并有序链表的函数。我们首先判断l1和l2中是否有任何一个为空，如果有一个为空，则使用另一个链表作为结果。

我们为合并后的链表创建一个新的头节点，并定义一个指针p将其指向头节点。我们使用while循环来遍历l1和l2。将较小的值作为合并后的链表的下一个节点，同时移动指针。现在我们有两个指针，它们指向l1和l2中剩余的节点（如果有）。我们简单地将这些节点中的每一个都添加到结果链表的尾部。

最后，我们返回合并后链表的头节点。

在main()函数中，我们首先创建了两个有序链表，并使用mergeTwoLists()函数将它们合并为一个有序链表。我们将结果打印为一个数组。

在C++中，使用结构体定义链表是一项常见的任务。在程序中，我们定义了一个ListNode结构体，它包括一个val和一个next指针，用于指向下一个节点。

在这个程序中，我们使用了一个Solution类来实现合并有序链表的函数。这个类可以方便地将其它函数添加到这个类中，并且将数据和函数组合在一起，使程序更加清晰。

  
  

评论区

请求出错了