將兩個(gè)有序鏈表合并為一個(gè)新的有序鏈表并返回煌恢。新鏈表是通過(guò)拼接給定的兩個(gè)鏈表的所有節(jié)點(diǎn)組成的骇陈。
示例：
輸入：1->2->4, 1->3->4
輸出：1->1->2->3->4->4
思路
代碼的思路很明確，入?yún)⒕褪莾蓚€(gè)鏈表中需要比較的結(jié)點(diǎn)瑰抵，如果說(shuō)傳入的某一個(gè)結(jié)點(diǎn)為空你雌，則直接返回另一個(gè)入?yún)⒔Y(jié)點(diǎn)即可，如果說(shuō)傳入的結(jié)點(diǎn)均不為空二汛，則比較兩個(gè)結(jié)點(diǎn)所帶的數(shù)據(jù)的大小婿崭，將較小的結(jié)點(diǎn)返回拨拓，同時(shí)要注意到，代碼中用到了遞歸氓栈，這點(diǎn)比較好理解渣磷，因?yàn)閷?duì)于我們需要合并的某一個(gè)結(jié)點(diǎn)來(lái)說(shuō)，完成一次合并后授瘦，其下一個(gè)結(jié)點(diǎn)醋界，自然也能用相同的方法來(lái)找到，這樣就找到了遞歸開(kāi)始的條件奥务，作為一個(gè)遞歸算法物独，還需要找到遞歸結(jié)束的條件，代碼一開(kāi)始的判斷氯葬，如果說(shuō)有一個(gè)入?yún)榭盏猜ǎ@說(shuō)明已經(jīng)到鏈表末尾，如果說(shuō)兩個(gè)入?yún)⒕鶠榭罩愠疲@說(shuō)明已經(jīng)遍歷完兩個(gè)鏈表官研，整個(gè)遞歸結(jié)束，合并完成闯睹。
代碼實(shí)現(xiàn)
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l1 == null) {
return l2;
}
if (l2 == null) {
return l1;
}
ListNode resultNode = null;
if (l1.val < l2.val) {
resultNode = l1;
resultNode.next = mergeTwoLists(l1.next, l2);
} else {
resultNode = l2;
resultNode.next = mergeTwoLists(l1, l2.next);
}
return resultNode;
}
}
