C++实现合并两个排序的链表
本文实例为大家分享了C++合并两个排序的链表，供大家参考，具体内容如下
问题描述
输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。
structListNode{
intval;
structListNode*next;
ListNode(intx):
val(x),next(NULL){
}
};
方法一
classSolution{
public:
ListNode*Merge(ListNode*pHead1,ListNode*pHead2)
{
ListNode*newList=NULL;//新链表头
ListNode*newListRear=NULL;//新链表尾
//先处理某个链表为空的情形
if(pHead1==NULL){
returnpHead2;
}
if(pHead2==NULL){
returnpHead1;
}
//把数值小的结点放入新链表，生成头节点
if(pHead1->val<=pHead2->val){
newList=pHead1;
newListRear=pHead1;
pHead1=pHead1->next;
}else{
newList=pHead2;
newListRear=pHead2;
pHead2=pHead2->next;
}
//两表均不空的情形下，遍历
while(pHead1!=NULL&&pHead2!=NULL){
if(pHead1->val<=pHead2->val){
newListRear->next=pHead1;
newListRear=pHead1;
pHead1=pHead1->next;
}else{
newListRear->next=pHead2;
newListRear=pHead2;
pHead2=pHead2->next;
}
}
//某一表为空时，把另一表接入新表表尾
if(pHead1==NULL){
newListRear->next=pHead2;
}
if(pHead2==NULL){
newListRear->next=pHead1;
}
returnnewList;
}
};
方法二（递归思想）
classSolution{
public:
ListNode*Merge(ListNode*pHead1,ListNode*pHead2)
{
if(pHead1==NULL){
returnpHead2;
}
if(pHead2==NULL){
returnpHead1;
}
if(pHead1->val<=pHead2->val){//pHead1为合并后的头节点
pHead1->next=Merge(pHead1->next,pHead2);
returnpHead1;
}else{//pHead2为合并后的头节点
pHead2->next=Merge(pHead1,pHead2->next);
returnpHead2;
}
}
};
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持毛票票。