题目描述：

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

 

解题思路：

这道题应该考察也是链表的相关操作。具体实现，新建一个新的链表，用两个指针分别指向两个链表，每次都比较两个指针指向的值，取小的加入新链表，同时当前指针后移一位。循环结束的条件为任意一个链表为空，即停止。最后做一个判断，新链表指向还没为空的单调递增链表。

 

代码：

/*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)            return pHead2;        if(pHead2 == nullptr)            return pHead1;        ListNode* new_pHead, *cur1=pHead1, *cur2=pHead2, *tmp;        if(pHead1->val < pHead2->val)        {            new_pHead = pHead1;            cur1 = cur1->next;        }        else        {            new_pHead = pHead2;            cur2 = cur2->next;        }        tmp = new_pHead;        while(cur1!=nullptr && cur2!=nullptr)        {            if(cur1->val < cur2->val)            {                tmp->next = cur1;                cur1= cur1->next;            }            else            {                tmp->next = cur2;                cur2 = cur2->next;            }            tmp = tmp->next;        }        if(cur1==nullptr)            tmp->next = cur2;        else if(cur2==nullptr)            tmp->next = cur1;        else            tmp->next = nullptr;        return new_pHead;    }};