C++实现两个有序链表的合并 |21xrx.com

C++实现两个有序链表的合并

2023-06-30 15:51:06 深夜i -- --

C++ 有序链表合并

C++是一种高级编程语言，常用于开发各种应用程序。其中，一个常见的应用是链表，是一种数据结构，用于存储一系列元素。当需求是合并两个有序链表时，使用C++来实现就非常方便。

有序链表的合并主要是将两个有序链表中的元素有序地插入新的链表中。由于链表是动态的，它们的大小不需要提前预定。下面，我们就从合并两个有序链表的C++实现来详细讲解。

首先，定义一个链表结构体，包含链表节点值和指向下一个节点的指针。如下所示：


struct ListNode{
 int val;
 ListNode* next;
 ListNode(int x)：val(x), next(NULL) {}
};

接着，我们定义一个新的链表和两个指针，分别指向两个已有的有序链表的头部。设计如下所示：


ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
 ListNode* result = new ListNode(0); //定义新链表
 ListNode* p = result; //新链表指针
 ListNode* p1 = l1; //第一个链表指针
 ListNode* p2 = l2; //第二个链表指针
 while(p1!=NULL && p2!=NULL)
 
 //...
 return result->next;
}

接下来，我们在while循环中来实现有序链表的合并。由于链表是有序的，我们只需要比对两个链表头节点大小，将较小的节点插入到新链表中即可。新链表指针和被插入的链表指针都需要向后移动一个节点。代码如下：


while(p1!=NULL && p2!=NULL) {
  if(p1->val < p2->val)  //比较数值大小链表的合并
    p->next = p1;
    p1 = p1->next;
  
  else
    p->next = p2;
    p2 = p2->next;
  
  p = p->next;
}

当其中一个链表扫描结束时，我们只需要将另一个链表的剩余节点链接到新的链表后面即可。代码如下：


while(p1!=NULL)
  p->next = p1;
  p1 = p1->next;
  p = p->next;
while(p2!=NULL)
  p->next = p2;
  p2 = p2->next;
  p = p->next;

最后，我们只需要返回新链表的头指针即可。

完整的C++代码实现如下：


using namespace std;
struct ListNode{
 int val;
 ListNode* next;
 ListNode(int x)：val(x), next(NULL) {}
};
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
 ListNode* result = new ListNode(0);
 ListNode* p = result;
 ListNode* p1 = l1;
 ListNode* p2 = l2;
 while(p1!=NULL && p2!=NULL) {
  if(p1->val < p2->val)
   p->next = p1;
   p1 = p1->next;
  
  else
   p->next = p2;
   p2 = p2->next;
  
  p = p->next;
 }
 while(p1!=NULL)
  p->next = p1;
  p1 = p1->next;
  p = p->next;
 
 while(p2!=NULL)
  p->next = p2;
  p2 = p2->next;
  p = p->next;
 
 return result->next;
}
int main() {
 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 = mergeTwoLists(l1, l2);
 while(result)
  cout << result->val << " ";
  result = result->next;
 
 return 0;
}

综上所述，C++实现两个有序链表的合并非常简单，只需要设计好链表结构体和指针即可。在本文中，我们通过定义链表结构体、指针和while循环来实现了有序链表的合并，希望对您有所帮助！

上一篇: idea打包java可执行jar包

下一篇: C++ A+B 代码实现

评论区

()

相似文章