21xrx.com
2024-12-22 23:06:40 Sunday
登录
文章检索 我的文章 写文章
C++实现合并有序链表
2023-06-26 16:14:41 深夜i     --     --
C++ 合并 有序链表 实现 数据结构

链表是一种重要的数据结构,常用于实现各种算法。在本文中,我们将介绍如何使用C++语言来实现合并有序链表。

有序链表定义为按照升序排列的链表。合并有序链表指的是将两个有序链表合并成一个新的有序链表。具体来说,我们需要将原始链表中的每个节点按照升序排列,然后重新构建一个新的链表。

下面是使用C++语言实现合并有序链表的一般步骤:

1. 创建一个新的链表

2. 遍历两个有序链表

3. 选择一个值较小的节点,并将其添加到新的链表中

4. 继续遍历剩余的节点,直到两个链表中的所有节点全部处理完成。

5. 返回新链表

具体实现过程如下:

 C++

#include <iostream>

using namespace std;

struct ListNode {

  int val;

  ListNode* next;

  ListNode(int x) : val(x), next(NULL) {}

};

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {

  ListNode* dummy = new ListNode(-1); // 创建一个哑节点

  ListNode* cur = dummy; // 当前节点指向哑节点

  while (l1 != NULL && l2 != NULL) {

    if (l1->val < l2->val) // 比较两个链表当前节点的大小 else

      cur->next = l2;

      l2 = l2->next;

    

    cur = cur->next;

  }

  // 将未处理完的链表剩余部分拼接到新链表中

  if (l1 != NULL)

    cur->next = l1;

   else

    cur->next = l2;

  

  return dummy->next;

}

int main() {

  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* mergeList = mergeTwoLists(l1, l2);

  ListNode* cur = mergeList;

  while (cur != NULL)

    cout << cur->val << " ";

    cur = cur->next;

  

  cout << endl;

  return 0;

}

在上面的代码中,我们首先创建了一个哑节点,并将当前节点指向哑节点。然后,我们遍历每个链表,并根据每个节点的大小将其添加到新链表中。最后根据未处理完的链表剩余部分,将其拼接到新链表中。

执行上述代码,输出结果如下:


1 2 3 4 5 6

我们可以看到,合并后的链表已经按照升序排列了。

  
  

评论区

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