題目

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

示例：

輸入：1->2->4, 1->3->4

輸出：1->1->2->3->4->4

思路

每次比較兩個鏈表的值的操作很適合遞歸，如果有值，則繼續(xù)遞歸比較，選擇較小的值保存到鏈表中，直到一個鏈表為null。

代碼

class ListNode{
    int val;
    ListNode next;
 
    ListNode(int x){
        val = x;
    }
}

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) return l2;
        if (l2 == null) return l1;
 
        ListNode head = null;
        if (l1.val <= l2.val){
            head = l1;
            head.next = mergeTwoLists(l1.next, l2);
        } else {
            head = l2;
            head.next = mergeTwoLists(l1, l2.next);
        }
        return head;
}