题目描述：
输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。
解题思路：
这道题应该考察也是链表的相关操作。具体实现，新建一个新的链表，用两个指针分别指向两个链表，每次都比较两个指针指向的值，取小的加入新链表，同时当前指针后移一位。循环结束的条件为任意一个链表为空，即停止。最后做一个判断，新链表指向还没为空的单调递增链表。
代码：
/*
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;
}
};