C++怎么合并两个排序的链表

本篇内容主要讲解"C++怎么合并两个排序的链表"，感兴趣的朋友不妨来看看。本文介绍的方法操作简单快捷，实用性强。下面就让小编来带大家学习"C++怎么合并两个排序的链表"吧!

题目描述：

输入两个递增的链表，单个链表的长度为n，合并这两个链表并使新链表中的节点仍然是递增排序的。

数据范围： n为0~1000，节点值为-1000~1000

要求：空间复杂度 O(1)，时间复杂度 O(n)

如输入{1,3,5},{2,4,6}时，合并后的链表为{1,2,3,4,5,6}，所以对应的输出为{1,2,3,4,5,6}，转换过程如下图所示：

或输入{-1,2,4},{1,3,4}时，合并后的链表为{-1,1,2,3,4,4}，所以对应的输出为{-1,1,2,3,4,4}，转换过程如下图所示：

示例：

输入：

{1,3,5},{2,4,6}

返回值：

{1,2,3,4,5,6}

解题思路：

本题考察数据结构链表的使用。有两种解法：

1. 遍历比较。建立一个新的头节点head后，用cur指针指向下一节点；然后依次比较两个子链表节点的值大小，谁小先塞谁，塞完就将其指向下一个节点；直到某个子链表遍历完，将cur的next指向没遍历完的那个链表当前的节点。

2. 递归。从pHead1和pHead2的头节点开始比较，谁小就返回谁，然后其下一个指向，指向Merge函数的结果，Merge输入的两个链表为小的一方的next和大的一方的头节点，也就是用下一个值和它继续比谁更小；依次类推，递归中断的标志是有其中一个子链表指向nullptr，返回另一方即可。

测试代码：

解法一，遍历：

/*struct ListNode {        int val;        struct ListNode *next;        ListNode(int x) :                        val(x), next(NULL) {        }};*/class Solution {public:    ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {        ListNode *head=new ListNode(-1);        ListNode *cur=head;        while(pHead1&&pHead2)        {            if(pHead1->val<=pHead2->val)            {                cur->next=pHead1;                pHead1=pHead1->next;            }            else{                cur->next=pHead2;                pHead2=pHead2->next;            }            cur=cur->next;        }        cur->next=pHead1?pHead1:pHead2;        return head->next;    }};

解法二，递归：

/*struct ListNode {        int val;        struct ListNode *next;        ListNode(int x) :                        val(x), next(NULL) {        }};*/class Solution {public:    ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {        if(!pHead1)            return pHead2;        if(!pHead2)            return pHead1;        if(pHead1->val<=pHead2->val)        {            pHead1->next=Merge(pHead1->next,pHead2);            return pHead1;        }        else{            pHead2->next=Merge(pHead1,pHead2->next);            return pHead2;        }    }};

到此，相信大家对"C++怎么合并两个排序的链表"有了更深的了解，不妨来实际操作一番吧！这里是网站，更多相关内容可以进入相关频道进行查询，关注我们，继续学习！