21xrx.com
2024-11-05 18:35:38 Tuesday
登录
文章检索 我的文章 写文章
C++合并两个有序链表的序列
2023-07-13 18:57:43 深夜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) {

    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类来实现合并有序链表的函数。这个类可以方便地将其它函数添加到这个类中,并且将数据和函数组合在一起,使程序更加清晰。

  
  

评论区

{{item['qq_nickname']}}
()
回复
回复