合并两个排序的链表

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;
    }
};