题解 | #合并两个排序的链表#

从链表1和链表2的头部选择一个小的节点插入到新节点中，new_head记录新链表的头部，new_tail记录新链表的尾部。第一个插入的节点就是new_head，每次插入都去更新new_tail。某一个链表结束以后，总有一个链表剩下某些节点，再进行遍历插入即可

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
            val(x), next(NULL) {
    }
};*/
class Solution {
public:
    ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {

        //插入某个结点以后，下一次插入只可能是在已经插入的节点之后;
        ListNode* new_head = NULL;
        ListNode* new_tail = NULL;

        //若节点pHead1为空则直接返回pHead2;
        if(!pHead1)
        {
            return pHead2;
        }
        //若节点pHead2为空则直接返回pHead1;
        if(!pHead2)
        {
            return pHead1;
        }

        ListNode* p = pHead1;
        ListNode* q = pHead2;
        while(p && q)
        {
            //将较小的插入到最前面;
            if(p->val < q->val)
            {
                //临时保存下一个节点;
                ListNode* tmp = p->next;
                //获取头节点;
                if(!new_head)
                {
                    new_head = p;
                    new_tail = new_head;
                }else
                {
                    //将当前节点p插入到尾节点后面;
                    new_tail = insert(new_tail,p);
                }
                //节点p指向下一个节点;
                p = tmp;
            }else
            {
                //临时保存下一个节点;
                ListNode* tmp = q->next;
                //获取头节点;
                if(!new_head)
                {
                    new_head = q;
                    new_tail = new_head;
                }else
                {
                    //将当前节点q插入到尾节点后面;
                    new_tail = insert(new_tail,q);
                }
                //节点q指向下一个节点;
                q = tmp;
            }
            //尾节点的下一个节点为空;
            new_tail->next = NULL;
        }

        //节点p的最大值比q大,所以链表p有剩余;
        while(p)
        {
            ListNode* tmp = p->next;
            new_tail = insert(new_tail,p);
            p = p->next;
        }
        //节点q的最大值比p大,所以链表q有剩余;
        while(q)
        {
            ListNode* tmp = q->next;
            new_tail = insert(new_tail,q);
            q = q->next;
        }
        return new_head;
    }

    //将节点p_node插入到链表尾部并返回更新后的链表尾;
    ListNode* insert(ListNode* tail, ListNode* p_node)
    {
        //如果尾节点为空,则直接赋值;
        if(!tail)
        {
            tail = p_node;
        }
        else
        {
            //向尾节点追加新的节点,并更新尾节点;
            tail->next = p_node;
            tail = tail->next;
        }
        //返回新的尾节点;
        return tail;
    }
};