先分析一下合并过程。假设链表1的头结点的值小于链表2的头结点的值，则链表1的头结点作为合并后的链表的头结点。然后继续合并两个链表中剩余的结点。两个链表中剩下的结点依然是排序的，所以合并这两个链表的步骤和前面的步骤一样。这是典型的递归过程，可以定义递归函数来完成这一合并过程。
这里写图片描述
private ListNode merge(ListNode pHead1,ListNode pHead2){
if (pHead1==null){
return pHead2;
}
if (pHead2==null){
return pHead1;
}
ListNode pMergedHead=null;
if (pHead1.getValue()<pHead2.getValue()){
pMergedHead=pHead1;
pMergedHead.setNext(merge(pHead1.getNext(),pHead2));
}else {
pMergedHead=pHead2;
pMergedHead.setNext(merge(pHead1,pHead2.getNext()));
}
return pMergedHead;
}
