21. Merge Two Sorted Lists

recursion:

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    if (l1 == null || l2 == null) 
        return (l1 != null) ? l1 : l2;

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

naive方法设置dummy node再比较大小。

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    ListNode p = new ListNode(0);
    ListNode head = p;
    while (l1 != null && l2 != null) {
        if (l1.val < l2.val) {
            p.next = new ListNode(l1.val);
            l1 = l1.next;
        } else {
            p.next = new ListNode(l2.val);
            l2 = l2.next;
        }
        p = p.next;
    }
    p.next = (l1 != null) ? l1 : l2;
    return head.next;
}