合并两个递增排序的链表，合并后仍递增有序。

这是面试中经常被提到的问题。下图表示链表1和链表2合并成链表3：

1.用递归算法更加简单好理解，即链表1的头结点值小于链表2头结点的值，我们就将链表1作为合并后链表的头结点，在剩余结点中，链表2的头结点值小于链表1头结点的值，我们将链表二的头结点作为合并链表的后续结点，且剩余结点依然是有序的，合并的步骤和之前一样，如下图：

递归代码如下：

ListNode* Merge(ListNode* pHead1,ListNode* phead2)
{
	if(pHead1 == NULL)
		return pHead2;
	else if(pHead2 == NULL)
		return pHead1;
	ListNode* pMergedHead = NULL;

	if(phead1 -> m_nValue < pHead2 -> m_nValue)
	{
		pMergedHead = pHead1;
		pMergedHead -> m_pNext = Merge(pHead1 -> m_pNext , pHead2);
	}
	else
	{
		pMergedHead = pHead2;
		pMergedHead -> m_pNext = Merge(pHead1,pHead2 -> m_pNext);
	}
	return pMergedHead;
}

2.用指针分别指向两个链表的第一个节点，比较大小，那个大，将元素尾插进入我所要返回的新链表中去。一次比较循环往复，直至某一个链表为空为止。但有可能会出现一个链表为空，另一个链表不为空。我们就要在最后检测，将不为空链表的全部挂在我要返回元素的后面。因为要不停的给新链表尾插。所以我用一个指针，将新链表的尾部标记。代码如下：

typedef int DataType;

typedef struct ListNode
{
	DataType _data;			//当前节点中所保存的元素
	struct ListNode* _pNext;	//指向链表中下一个结点

}SLinkList, SListNode;

SLinkList* MergeLinkListOP(SLinkList* pHead1, SLinkList* pHead2)
{
	SLinkList* New = NULL;//合并后的链表
	SLinkList* tail = NULL;//标记合并后链表的尾部，方便尾插
	SLinkList* cur1 = pHead1;
	SLinkList* cur2 = pHead2;
	SLinkList* nxt = NULL;//用来保存链表的后续节点
	SLinkList* node = NULL;
	while (cur1 != NULL && cur2 != NULL)
	{
		if (cur1->_data <= cur2->_data)
		{
			node = cur1;//应取链表1的结点
		}
		else
		{
			node = cur2;
		}
		
		nxt = node->_pNext;//保存cur1后面的节点:将cur1指向的结点从链表1上取下来，挂在新链表上，后序的链表应该保存下来，否则程序会奔溃
		if (New == NULL)//合并的链表为空
		{	
			New = node;//将cur1指向的结点挂在新链表上
		}
		else//合并链表不为空
		{	
			tail->_pNext = node;
		}
		node->_pNext = NULL;//尾插，链表的最后一个元素应为空
		tail = node;//保存新链表的最后一个节点
		if (node == cur1)//已经将节点挂在新链表上，循环应该让cur1 和 cur2改变，因此在这里应该让cur前进
		{
			cur1 = nxt;
		}
		else
		{
			cur2 = nxt;
		}
	}	
	if (cur1 == NULL)//一个链表空了，但要判断里另一个链表为不为空
		tail->_pNext = cur2;
	if (cur2 == NULL)
		tail->_pNext = cur1;

	return New;
}