21xrx.com
2024-11-05 20:34:15 Tuesday
登录
文章检索 我的文章 写文章
C++完整代码:合并两个有序链表
2023-06-25 05:24:20 深夜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即为新链表的头节点。

  
  

评论区

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