###### tags: `LeetCode`,`Java`,`Easy`
# Easy－21. Merge Two Sorted Lists
### **題目連結：** [**Merge Two Sorted Lists**](https://leetcode.com/problems/merge-two-sorted-lists/description/)

### **解題方向**
* 這題是考你鏈結串列的邏輯，這類題目建議畫圖會比較好懂！
* 我的做法是遞迴，也是我認為比較簡單的解法！
* 一開始先判斷某個list是否為空，若是則return另一個list，而這也是我設的終止條件。
* 接下來就是用遞迴的方式一一把最小值拉出來即可算出正解。
* 第20跟25是印出要被return的值，會讓你比較好理解return順序。

**鍊結串列順序圖**
**鍊結串列順序圖－樹狀圖版**

### **完整程式碼**

/**
 * 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);
            //System.out.println(list1.val);
            return list1;
        } else {
            list2.next = mergeTwoLists(list1, list2.next);
            //System.out.println(list2.val);
            return list2;
        }
    }
}