题目描述：

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

实现如下：

//本题在线测试用例怎么还是无头节点链表→_→，啊...
//比较value谁小谁添加到新链表中
//新链表的头节点指针为newHead，由s指针负责添加信节点
//特殊情况：
//1.传入空指针
//2.任意一个链表添加完毕
//3.传入的一个链表为空，另一个不为空
//节点结构体定义
/*
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 == NULL && pHead2 == NULL)return NULL;
		ListNode *newHead = NULL;//新链表的头指针
		ListNode *s = NULL;//负责给新链表添加心节点
		while (pHead1 != NULL && pHead2 != NULL)//直到将一个链表添加完
		{
			if (pHead1->val <= pHead2->val)//谁小谁添加
			{
				if (newHead == s && newHead == NULL)//第一次添加节点
				{
					newHead = pHead1;
					s = pHead1;
				}
				else//除第一次以外添加节点
				{
					s->next = pHead1;
					s = s->next;
				}
				pHead1 = pHead1->next;//使pHead1指向为排序节点
			}
			else
			{
				if (newHead == s && newHead == NULL)//第一次添加节点情况
				{
					newHead = pHead2;
					s = pHead2;
				}
				else//除第一次情况以外
				{
					s->next = pHead2;
					s = s->next;
				}
				pHead2 = pHead2->next;
			}
		}
		//判断是否为一个为空另一个不为空的情况
		if (newHead == NULL && pHead1 != NULL) newHead = pHead1;
		else if (newHead == NULL && pHead2 != NULL) newHead = pHead2;
		else if (pHead1 != NULL) s->next = pHead1;//判断是否还有链表未添加完
		else if (pHead2 != NULL)s->next = pHead2;
		return newHead;
	}
};