题解 | #合并两个排序的链表#

function ListNode(x){
    this.val = x;
    this.next = null;
}

// Recursion
function Merge(l1, l2) {
    if (!l1) return l2;
    if (!l2) return l1;
    if (l1.val < l2.val) {
        l1.next = Merge(l1.next, l2); // the next part is magic done;
        return l1;
    } else {
        l2.next = Merge(l1, l2.next);
        return l2
    }
}

// Iteration
function Merge(l1, l2) {
    let dummy  = new ListNode(0);
    let p = dummy;
    while (l1 && l2) {
        if (l1.val < l2.val) {
            p.next = l1;
            l1 = l1.next; 
        } else {
            p.next = l2;
            l2 = l2.next; 
        }
        p = p.next;
    }
    // append the left part
    if (l1) p.next = l1; 
    if (l2) p.next = l2;
    
    return dummy.next;
}

module.exports = {
    Merge : Merge
};