時月oe

題目來源：合并兩個有序鏈表

兩個鏈表有序，這個很類似于歸并排序的歸并過程，但是數組的歸并過程會創建一個臨時數組，這里如果創建一個臨時鏈表開銷就比較大了，因此需要考慮原地排序算法

非遞歸方案

首先我們定義一個ans節點，用來保存排序后的頭節點

然后定義一個prev節點，表示經過排序后的當前節點

首先比較list1和list2的val大小，讓prev.next指向較小的那個，然后讓較小的那個后移

然后prev = prev.next，繼續執行比較的操作

直到list1或者list2為空，最后記得讓prev.next指向不為空的那個節點

最后返回的時候，返回ans.next即可

/**
 * 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) {
        ListNode ans = new ListNode();
        ListNode prev = ans;

        while(list1 != null && list2 != null){
            if(list1.val < list2.val){
                prev.next = list1;      //將前面排序好的節點的next指向list
                list1 = list1.next;      //讓小的那個指針后移
                prev = prev.next;     //更新prev，使其指向最近更新的那個節點
            }else{
                prev.next = list2;
                list2 = list2.next;
                prev = prev.next;
            }
        }
        if(list1 != null)prev.next = list1;           //最后記得把沒走完的那個鏈表接上
        if(list2 != null)prev.next = list2;
        return ans.next;
    }
}

遞歸方案

使用遞歸解決的思路就是：
既然這個函數返回的是排序好的鏈表的頭節點，那么

• 如果list1.val < list2.val，那么list1.next = mergeTwoLists(list1.next,list2)
• 如果list2.val < list1.val，那么list2.next = mergeTwoLists(list1,list2.next)

最后遞歸終止的條件

• 如果list1 == null，那么就返回list2
• 如果list2 == null，那么就返回list1

/**
 * 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(list1,list2.next);
            return list2;
        }
    }
}