21xrx.com
2024-11-05 18:30:37 Tuesday
登录
文章检索 我的文章 写文章
C++单链表合并的实现方法
2023-07-03 07:33:33 深夜i     --     --
C++ 单链表 合并 实现方法

单链表是一种基本的数据结构,为了更好地利用单链表,有时需要把两个单链表合并成一个链表。这种操作在实际中非常常见。在C++中,单链表合并也是一种常见的操作,下面介绍一下C++单链表合并的实现方法。

C++中单链表通常是通过指针来实现的,因此在合并两个单链表时,需要对它们的指针进行操作。具体步骤如下:

1. 创建两个单链表ListA和ListB,假设它们分别包含m个元素和n个元素。

2. 定义一个新的单链表ListC,用于存放合并后的结果。

3. 从ListA和ListB中依次取出节点,比较它们的值的大小,并将较小的节点插入到ListC中。

4. 如果有一个链表已经到达了末尾,则将另一个链表中剩余的节点依次插入到ListC中。

5. 最后返回ListC,即为合并后的结果。

下面是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 *head, *tail;

  head = tail = new ListNode(0);

  while (l1 && l2) {

    if (l1->val < l2->val)

      tail->next = l1;

      l1 = l1->next;

     else

      tail->next = l2;

      l2 = l2->next;

    

    tail = tail->next;

  }

  if (l1) tail->next = l1;

  if (l2) tail->next = l2;

  return head->next;

}

int main() {

  ListNode *l1 = new ListNode(1);

  ListNode *l1_1 = new ListNode(3);

  ListNode *l1_2 = new ListNode(5);

  l1->next = l1_1;

  l1_1->next = l1_2;

  

  ListNode *l2 = new ListNode(2);

  ListNode *l2_1 = new ListNode(4);

  ListNode *l2_2 = new ListNode(6);

  l2->next = l2_1;

  l2_1->next = l2_2;

  ListNode *l3 = mergeTwoLists(l1, l2);

  while (l3)

    cout << l3->val << " ";

    l3 = l3->next;

  

  return 0;

}

上述代码中,ListNode结构体用于封装每个节点的值和指针。mergeTwoLists函数用于合并两个链表,返回合并后的链表。在函数内部,定义了一个头节点和尾节点,用于构建新的链表。while循环中比较l1和l2的值的大小,依次插入到新链表中。最后,将剩余的节点插入到新链表中,并返回头节点的next,这样就得到了合并后的链表。

总之,C++单链表的合并是比较常见的操作,关键是要熟练掌握指针的相关知识。通过上述实现方法,能够方便地将两个单链表合并成一个链表,方便后续的处理。

  
  

评论区

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