1.題目

將兩個升序鏈表合并為一個新的 升序 鏈表并返回。新鏈表是通過拼接給定的兩個鏈表的所有節點組成的。?

2.示例

示例 1：

輸入：l1 = [1,2,4], l2 = [1,3,4]
輸出：[1,1,2,3,4,4]?

?示例 2：

輸入：l1 = [], l2 = []
輸出：[]

示例 3：?

輸入：l1 = [], l2 = [0]
輸出：[0]

---

3.思路

遞歸調用

將這個問題不斷拆分成子問題，然后設置出口。由題目可以知道，合并兩個鏈表，首先需要比較兩個鏈表中的元素，將元素小的拆分出來然后拼接到后續組合好的鏈表中。如此反復直到最后一個一個元素。

4.代碼

LeetCode代碼

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode mergeTwoLists(ListNode list1, ListNode list2) {// 出口if(list1 == null){return list2;}if(list2 == null){return list1;}// 子問題if(list1.val<list2.val){list1.next = mergeTwoLists(list1.next,list2);return list1;}else{list2.next = mergeTwoLists(list2.next,list1);return list2;}}
}

---

?會了？試試挑戰下一題！?（＾?＾●）ﾉｼ （●′?｀）?

LeetCode150道面試經典題-- 加一(簡單)_Alphamilk的博客-CSDN博客