首页 > 编程语言 > 详细

合并两个排序的链表

时间:2019-08-20 22:15:30      阅读:92      评论:0      收藏:0      [点我收藏+]

1.递归求解

/*
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==nullptr &&pHead2==nullptr)
        return  nullptr;  
        if(pHead1==nullptr)
        return pHead2;
        if(pHead2==nullptr)
        return pHead1;
        
        //开始递归求   //要定义一个辅助的量  将排好序的放在里面
        ListNode* pMergehead=nullptr;//归并后的
       if(pHead1->val<=pHead2->val) 
        {
           pMergehead=pHead1; 
           pMergehead->next= Merge(pHead1->next,pHead2);//递归一般都于高向低 内部
        }
        else {
            pMergehead=pHead2;
            pMergehead->next= Merge(pHead1,pHead2->next);
        }
   
    return  pMergehead;
    }
};

2. 非递归    注意顺序 将==NULL放在最后,  满足的也是一开始就进去了!!!

/*
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);
        head->next=NULL;
        ListNode * root=head;
        while(pHead1!=NULL&&pHead2!=NULL){//都不为null
            if(pHead1->val<pHead2->val){
                head->next=pHead1;
                head=head->next;
                pHead1=pHead1->next;
            }else{
                head->next=pHead2;
                head=head->next;
                pHead2=pHead2->next;
            }
        }
        //把未结束的链表连接到合并后的链表尾部
        if(pHead1!=NULL){
            head->next=pHead1;
        }
        if(pHead2!=NULL){
            head->next=pHead2;
        }
        return root->next;
    }
};

 

合并两个排序的链表

原文:https://www.cnblogs.com/cgy1012/p/11385622.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!