題目描述
兩個升序鏈表合并為一個新的升序鏈表。
示例：
輸入：1->2->4, 1->3->4
輸出：1->1->2->3->4->4
解析
考察重點：迭代實現(xiàn)與遞歸實現(xiàn)
實現(xiàn)方法
- 方法一：迭代實現(xiàn)很簡單，兩個指針分別遍歷兩個鏈表，比較當前結點的大小，依次鏈接到新表上即可洗做。
- 方法二：遞歸實現(xiàn)驯嘱，遞歸是算法設計中常用的技巧灶壶，函數(shù)調用自己本身义郑，局部求解最后得出全部求解。比較兩個鏈表的第一個結點丈钙，從鏈表中取下較小的元素的結點非驮，余下部分形成新的鏈表與另外一個鏈表再做合并，依次遞歸雏赦。
實現(xiàn)技巧：
遞歸實現(xiàn)在算法設計中得到廣泛的應用劫笙。
迭代實現(xiàn)代碼
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
/*如果其中一個鏈表為null，則返回另一個鏈表即可*/
if(l1 == null){
return l2;
}
if(l2 == null){
return l1;
}
ListNode head = new ListNode(-1);//定義結果的頭結點
ListNode tail = head;//定義結果的尾指針
while(l1 != null && l2 != null){//遍歷兩個鏈表按照數(shù)據(jù)升序鏈接到新的鏈表中
if(l1.val < l2.val){
tail.next = l1;
tail = tail.next;
l1 = l1.next;
}else {
tail.next = l2;
tail = tail.next;
l2 = l2.next;
}
}
/*其中一個鏈表先遍歷完全星岗，另外一個鏈表鏈接到新表尾部即可*/
if(l1 == null){
tail.next = l2;
}else{
tail.next = l1;
}
ListNode res = head.next;//指向新表的第一個結點
head.next = null;//幫助GC回收head結點
return res;
}
遞歸實現(xiàn)代碼
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
/*遞歸結束的條件填大，如果有一個鏈表為null，則返回另一個鏈表俏橘，不再執(zhí)行遞歸操作*/
if(l1 == null){
return l2;
}
if(l2 == null){
return l1;
}
/*定義res指向兩個鏈表中元素較小的結點*/
ListNode res;
/*取出元素較小結點允华，余下部分組成新的鏈表*/
if(l1.val < l2.val){
res = l1;
l1 = l1.next;//余下部分組成新的鏈表l1
}else {
res = l2;
l2 = l2.next;//余下部分組成新的鏈表l2
}
res.next = mergeTwoLists(l1, l2);//遞歸調用，res的next指向新的兩個鏈表合并結果
return res;
}
總結
迭代實現(xiàn)易于理解寥掐、編碼復雜靴寂，遞歸實現(xiàn)編碼簡單，但對于初學者難理解召耘。不過兩種方法都是算法設計中的重點百炬，更好的掌握和理解對于解決問題很有用。未來還會遇到其他的需要兩種方法實現(xiàn)的算法污它，例如最經(jīng)典的就是樹的遍歷剖踊，遞歸實現(xiàn)和迭代實現(xiàn)（非遞歸實現(xiàn)）庶弃。
