剑指offer25:合并两个排序的链表

题目：输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则.

思路：对于两个递增的链表合并，合并后仍递增. 取两个链表中最小头节点作为新的头节点. 然后依次取两个链表中最小的节点链接到新头节点后.

ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
    {
        if(pHead1==nullptr)
            return pHead2;
        if(pHead2==nullptr)
            return pHead1;
        ListNode* p1;
        ListNode* p2;
        //p1指向头节点最小的链表
        if(pHead1->val<=pHead2->val){
            p1=pHead1;
            p2=pHead2;}
        else{
            p1=pHead2;
            p2=pHead1;
        }
        ListNode* newHead=p1;
        ListNode* newTail=newHead;
        p1=p1->next;
        //每次取当前最小节点插入尾节点后
        while(p1!=nullptr && p2!=nullptr){
            if(p1->val <=p2->val){
                newTail->next=p1;
                p1=p1->next;
            }else{
                newTail->next=p2;
                p2=p2->next;
            }
            newTail=newTail->next;
            newTail->next=nullptr;
        }
        if(p1==nullptr && p2!=nullptr)
            newTail->next=p2;
        if(p1!=nullptr && p2==nullptr)
            newTail->next=p1;
        return newHead;
    }

上诉代码每次取当前最小值，然后对剩下的序列进行相同的操作，可以使用递归实现.

ListNode* Merge(ListNode* pHead1, ListNode* pHead2){
    if(pHead1==nullptr)
        return pHead2;
    if(pHead2==nullptr)
        return pHead1;
    ListNode* mergeNode=nullptr;
    if(pHead1->val < pHead2->val){
        mergeNode = pHead1;
        mergeNode->next = Merge(pHead1->next, pHead2);
    }
    else{
        mergeNode = pHead2;
        mergeNode->next = Merge(pHead1, pHead2->next);
    }
    return mergeNode;
}