合并两个排序的链表（Java）

题目：

输入两个递增排序的链表，合并这两个链表并使新链表中的结点仍然是按照递增排序的。例如：输入下图中的链表1和链表2，则合并之后的升序链表如链表3所示。链表的结点定义如下：

struct ListNode{
	int m_nValue;
	ListNode* m_pNext;
}

思路：

在合并两个链表的过程中。链表1的头结点的值小于链表2的头结点的值，因此链表1的头结点将是合并后链表的头结点。继续合并时，链表中剩下的结点依然是排序的，因此合并这两个链表的步骤和上面的是一模一样：还是比较两个头结点的值，此时链表2的头结点值小于链表1头结点的值，因此链表2的头结点的值将是合并剩余结点得到的链表的头结点。我们把这个结点和前面合并链表时得到的链表的尾结点（值为1的结点）链接起来。

当我们得到两个链表中值较小的头结点并把它链接到已经合并的链表之后，两个链表剩余的结点依然是排序的，因此合并的步骤和之前的步骤是一样的。故典型的递归解决在招手。

递归代码实现：

public class ListNode {
	public int data;
	public ListNode next;
}

public ListNode merge(ListNode pHead1, ListNode pHead2){
	if(pHead1 == null){
		return pHead2;
	}else if(pHead2 == null){
		return pHead1;
	}
	ListNode pMergeHead = null;
	if(pHead1.data < pHead2.data){
		pMergeHead = pHead1;
		pMergeHead.next = merge(pHead1.next, pHead2);
	}else{
		pMergeHead = pHead2;
		pMergeHead.next = merge(pHead1, pHead2.next);
	}
	return pMergeHead;
}

非递归代码实现：

public ListNode merge1(ListNode pHead1, ListNode pHead2){
	if(pHead1 == null){ //如果链表1为空或者链表1和2都为空则直接返回链表2
		return pHead2;
	}else if(pHead2 == null){ //如果链表2为空直接返回链表1
		return pHead1;
	}
	ListNode pMergeHead = null;
	while(pHead1!=null && pHead2!=null){ //都不为空时一个一个结点判断
		if(pHead1.data < pHead2.data){ //链表1的结点小于链表2的结点，合并链表插入链表1的结点
			pMergeHead = pHead1;
			pHead1 = pHead1.next;
		}else{
			pMergeHead = pHead2;
			pHead2 = pHead2.next;
		}
		pMergeHead = pMergeHead.next;
		pMergeHead.next = null;
	}
	if(pHead1==null && pHead2!=null){ //直接插入链表2
		pMergeHead.next = pHead2;
	}else if(pHead1!=null && pHead2 ==null){ //直接插入链表1
		pMergeHead.next = pHead1;
	}
	return pMergeHead; //返回合并链表
}

小结：

这个题很容易犯两个错误：（1）在写代码之前没有对合并的过程想清楚，最终合并出来的链表要么中间断开了要么并没有做到递增排序；（2）代码鲁棒性方面存在问题，程序一旦有特殊输入（空链表）就会出现异常。