文字化表达

生成一个新链表用于保存合并后的有序链表。通过比较两个有序链表的节点值，来决定哪个节点应该被附加到新链表中。

迭代

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} list1
 * @param {ListNode} list2
 * @return {ListNode}
 */
var mergeTwoLists = function(list1, list2) {
    let newNode = new ListNode(0)
    // 为什么要这一句
    // 这个应该是复制一份当前节点位置，以用来不断此新链表
    // 因为最终在最后需要返回一个实现完的新链表，那就得返回该新链表的头节点
    
    let temp = newNode
    let n1 =list1, n2= list2

    while (n1 && n2) {
        if (n1.val > n2.val) {
            // n2链表的当前节点更小的情况

            temp.next = n2
            // 当把一个节点赋给另一个节点时，节点.next会随着带过去吗

            // 让n2链表向前走一步
            n2 = n2.next
        } else {
            // n1链表的当前节点更小的情况

            temp.next = n1
            n1 = n1.next
        }
        temp = temp.next
    }

    // 上面while的进入条件是l1 l2的后续节点都不为null，那么这里就一定会还有一个链表的值没被处理完的情况
    // 这里不应该是n1.next !== null，因为上面已经将n1向前走了，所以此时应该判断n1是不是null，因为有可能遇到n1本身就是null的情况
    if (n1 !== null) {
        temp.next = n1
    }
    if (n2 !== null) {
        temp.next = n2
    }

    return newNode.next
};

递归解法

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

递归用得好，回家回得早。