先分析一下合并過程背桐。假設(shè)鏈表1的頭結(jié)點(diǎn)的值小于鏈表2的頭結(jié)點(diǎn)的值，則鏈表1的頭結(jié)點(diǎn)作為合并后的鏈表的頭結(jié)點(diǎn)照激。然后繼續(xù)合并兩個鏈表中剩余的結(jié)點(diǎn)。兩個鏈表中剩下的結(jié)點(diǎn)依然是排序的铃拇，所以合并這兩個鏈表的步驟和前面的步驟一樣钞瀑。這是典型的遞歸過程，可以定義遞歸函數(shù)來完成這一合并過程慷荔。
這里寫圖片描述
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;
}
