c++ 如何合并两个有序链表

2023-07-18 22:00:04 171

1.题目要求

这是一道求职面试时经常要求手写或者机试的经典题目。

已知两个链表head1和head2各自有序，请把它们合并成一个链表依然有序。结果链表要包含head1和head2的所有节点，即使节点值相同。

注意：不能开辟新空间来存储合并后的链表。如果第一次做该题，很容易会想到使用新链表来存储合并后的有序链表。虽然可以如此实现，但是不符合常规解法和面试官的要求。

2.非递归实现

算法过程：
输入：两个有序的单链表head1与head2；
输出：合并后的有序单链表mergeHead；
算法描述：
（1）如果head1或head2为空链表，则直接返回另外一个链表；
（2）选择head1与head2链表当前节点值较小的节点，挂接到后并后的链表mergeHead；
（3）重复步骤2，直到链表head1或者head2遍历完成，未遍历完的链表，直接挂接到mergeHead的尾节点。

具体实现如下：

#include
#include
usingnamespacestd;

structListNode
{
intvalue;
ListNode*next;
ListNode(){value=0;next=NULL;}
ListNode(intvalue,ListNode*next=NULL):value(value),next(next){}
};

//@brief:非递归实现两个有序单链表
//@注意：两个链表需要从小到大顺序排列
ListNode*mergeOrderedLinkedList(ListNode*head1,ListNode*head2)
{
if(head1==NULL)
{
returnhead2;
}
elseif(head2==NULL)
{
returnhead1;
}

ListNode*mergeHead=NULL;
if(head1->valuevalue)
{
mergeHead=head1;
head1=head1->next;
}
else
{
mergeHead=head2;
head2=head2->next;
}
ListNode*tmpNode=mergeHead;
while(head1&&head2)
{
if(head1->valuevalue)
{
mergeHead->next=head1;
head1=head1->next;
}
else
{
mergeHead->next=head2;
head2=head2->next;
}
mergeHead=mergeHead->next;
}
if(head1)
{
mergeHead->next=head1;
}
if(head2)
{
mergeHead->next=head2;
}

returntmpNode;
}

//打印链表
voidprintLinkedList(ListNode*head)
{
while(head)
{
cout<value<<"";
head=head->next;
}
cout<>value)//从string中按照空格读取int
{
ListNode*newNode1=newListNode;
newNode1->value=value;
if(head1==NULL&&curList1==NULL)
{
head1=newNode1;
curList1=newNode1;
}
else
{
curList1->next=newNode1;
curList1=curList1->next;
}
}

cout<<"创建链表2，从小到大顺序输入链表2："<>value)//从string中按照空格读取int
{
ListNode*newNode2=newListNode;
newNode2->value=value;
if(head2==NULL&&curList2==NULL)
{
head2=newNode2;
curList2=newNode2;
}
else
{
curList2->next=newNode2;
curList2=curList2->next;
}
}

//合并两个有序链表
ListNode*mergeHead=mergeOrderedLinkedList(head1,head2);

//打印链表
cout<<"合并后链表："<
运行程序，输出结果：

从小到大顺序输入链表1：

1235

ss0strIn:1235

从小到大顺序输入链表2：

345678

ss1strIn:345678

合并后链表：

1233455678

3.递归实现


从上面合并两个有序链表的步骤中可以看出，每次合并的步骤（2）都是一样的，由此我们想到了递归。具体实现如下：
//@brief:递归实现两个有序单链表
//@注意：两个链表需要从小到大顺序排列
ListNode*mergeOrderedLinkedListRecursion(ListNode*head1,ListNode*head2)
{
if(head1==NULL)
{
returnhead2;
}
elseif(head2==NULL)
{
returnhead1;
}

ListNode*mergeHead=NULL;
if(head1->valuevalue)
{
mergeHead=head1;
mergeHead->next=mergeOrderedLinkedListRecursion(head1->next,head2);
}
else
{
mergeHead=head2;
mergeHead->next=mergeOrderedLinkedListRecursion(head1,head2->next);
}
returnmergeHead;
}
以上就是c++如何合并两个有序链表的详细内容，更多关于c++合并两个有序链表的资料请关注毛票票其它相关文章！
声明：本文内容来源于网络，版权归原作者所有，内容由互联网用户自发贡献自行上传，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任。如果您发现有涉嫌版权的内容，欢迎发送邮件至：czq8825#qq.com（发邮件时，请将#更换为@）进行举报，并提供相关证据，一经查实，本站将立刻删除涉嫌侵权内容。

c++ 如何合并两个有序链表

热门推荐

随机推荐