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

C++ 实现有序链表合并

2023-06-25 13:17:47 深夜i -- --

C++ 有序链表合并

有序链表是指链表中的结点按照某种顺序排列，而有序链表合并则是将两个有序链表合并为一个有序链表。通过C++语言，我们可以轻松地实现有序链表合并的功能。

首先，我们需要定义一个链表结构体，包含一个数据域和一个指向下一个结点的指针域。


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

随后，我们利用递归的思想对两个有序链表进行合并。对于两个链表的第一个结点，我们比较它们的大小关系，将较小的那个结点作为合并后链表的头结点。然后我们递归调用merge函数，对较小结点的下一个结点和较大结点进行继续合并。当其中一个链表为空时，我们就直接将另一个链表剩余的部分连接到合并后的链表的尾部即可。


ListNode* merge(ListNode* l1, ListNode* l2){
  if(l1 == NULL)
    return l2;
  if(l2 == NULL)
    return l1;
  ListNode* head;
  if(l1->val < l2->val){
    head = l1;
    head->next = merge(l1->next, l2);
  }
  else{
    head = l2;
    head->next = merge(l1, l2->next);
  }
  return head;
}

最后，我们可以编写一个main函数来进行测试。


int main(){
  ListNode* l1 = new ListNode(1);
  l1->next = new ListNode(3);
  l1->next->next = new ListNode(5);
  l1->next->next->next = new ListNode(7);
  l1->next->next->next->next = new ListNode(9);
  ListNode* l2 = new ListNode(2);
  l2->next = new ListNode(4);
  l2->next->next = new ListNode(6);
  l2->next->next->next = new ListNode(8);
  ListNode* mergedList = merge(l1, l2);
  while(mergedList != NULL)
    cout << mergedList->val << " ";
    mergedList = mergedList->next;
  
  return 0;
}

执行结果为：

1 2 3 4 5 6 7 8 9

从结果可以看出，两个有序链表被成功地合并为了一个有序链表。

因此，C++实现有序链表合并并不是一件复杂的事情，只需要灵活应用链表结构体和递归思想，我们就可以很方便地完成这个任务。

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

下一篇: C++中将数字转化为字符的方法

评论区

()

相似文章