剑指offer面试题17-：合并两个排序链表

将两个已经排好序的链表（升序）进行合并，使得合并后的链表仍然有序。

假设两个链表分别为A和B，我的思路是将使用两个指针p和q扫描两个链表各一遍，将B链表中的元素插入到A中，最终形成一个新的链表。

边界条件：（1）链表为空时；

                  （2）开始时，A中第一个节点的值 < B中第一个节点的值；

                  （3）扫描完一个链表而另一个没有扫描完；

两个链表的初始状态：

由于B中第一个节点值为13比A中的小，所以将其作为A的第一个节点：

当p指向A中某个节点的值>q指向的值时，我们要借助于一个p的前驱指针pPre来改变指针的指向。详细代码如下：

linkNode* mergeLinkList(linkNode *&A, linkNode * &B)
{
	if (A == NULL)
		return B;
	if (B == NULL)
		return A;
	linkNode *p = A, *pPre = NULL;
	linkNode *q = B;
	while (p != NULL && q != NULL)
	{
		if (p->data <= q->data)//当p指向节点的值<=q指向的节点的值时，后移p指针
		{
			pPre = p;
			p = p->next;
		}
		else if (pPre == NULL)//说明链表A中的第一个节点中的值 < B链表中第一个节点值
		{
			linkNode *n = q->next;
			q->next = p;
			p = q;
			q = n;
			A = p;
		}
		else//p指向A的中间一个节点，p指向的值 > q指向的值
		{
			linkNode *n = q->next;
			pPre->next = q;
			q->next = p;
			pPre = q;
			q = n;
		}
	}
	if (q == NULL)//后续处理，当q为空时
		return A;
	else//p为空时
	{
		pPre->next = q;
		return A;
	}
}

假设A中有m个点，B中有n个节点，那么最坏情况下的时间是扫描一遍A和B所用的时间，即为O(m+n);