Merge Two Sorted Lists-LeetCode#21

21. Merge Two Sorted Lists

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.
Example:

Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4

合并两个排序后的链表
合并两个已排序的链接列表并将其作为新列表返回。新列表应该通过拼接前两个列表的节点来完成。
今天ac的几题都是用递归来做的…那这题直接就想到了递归
比较 l1 与 l2 的 val，把较小值赋值为next，每次递归 l1 与 l2 之间较小值的 next.

public class MergeTwoSortedLists {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        return dfs(l1, l2);
    }
    public ListNode dfs(ListNode l1, ListNode l2) {
        if (l1 == null){
            return l2;
        }
        if (l2 == null){
            return l1;
        }
        if (l1.val < l2.val) {
            l1.next = dfs(l1.next, l2);
            return l1;
        } else {
            l2.next = dfs(l1, l2.next);
            return l2;
        }
    }
    public static void main(String[] args) {
        ListNode l1 = new ListNode(1);
        l1.next = new ListNode(2);
        l1.next.next = new ListNode(4);
        ListNode k1 = new ListNode(1);
        k1.next = new ListNode(3);
        k1.next.next = new ListNode(4);
        MergeTwoSortedLists mergeTwoSortedLists = new MergeTwoSortedLists();
        mergeTwoSortedLists.mergeTwoLists(l1, k1);
    }
}
class ListNode {
    int val;
    ListNode next;
    ListNode(int x) {
        val = x;
    }
}