leetcode 21. 合并两个有序链表 js实现

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 

示例 1：

输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]

示例 2：

输入：l1 = [], l2 = []
输出：[]

示例 3：

输入：l1 = [], l2 = [0]
输出：[0]

提示：

• 两个链表的节点数目范围是 [0, 50]
• -100 <= Node.val <= 100
• l1 和 l2 均按 非递减顺序 排列

原题

/**
 * 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}
 */
// 迭代
// 时间复杂度：O(n+m)，其中 n 和 m 分别为两个链表的长度。因为每次调用递归都会去掉 l1 或者 l2 的头节点（直到至少有一个链表为空），函数 mergeTwoList 至多只会递归调用每个节点一次。因此，时间复杂度取决于合并后的链表长度，即 O(n+m)
// 空间复杂度：O(n+m)，其中 n 和 m 分别为两个链表的长度。递归调用 mergeTwoLists 函数时需要消耗栈空间，栈空间的大小取决于递归调用的深度。结束递归调用时 mergeTwoLists 函数最多调用 n+m 次，因此空间复杂度为 O(n+m)。
var mergeTwoLists = function(list1, list2) {
    if(!list1){
        return list2
    }
    if(!list2){
        return list1
    }
    // 定义一个空的链表
    let res = new ListNode(-1);
    // 复制该链表，因为迭代过程中会改变链表
    let ans = res;
    // 迭代结束条件为当一个链表遍历结束即停止
    while(list1&&list2){
        // 当list1节点大，则先指向list2 节点
        if(list1.val>=list2.val){
            res.next = list2;
            // 同时改变 list2 指针为下一个继续对比
            list2 = list2.next;
        }else{
            res.next = list1;
            list1 = list1.next;
        }
        // 每次迭代，改变当前链表的指向，以进行正确指向
        res = res.next;
    }
    // 最后迭代结束后，可能会有一个链表还有剩余，且由于是递增的，所以直接等于剩余的链表头节点即可
    res.next = list1?list1:list2;
    // 返回空节点的下一个即为最终的结果
    return ans.next;
};
// 递归  
// 空间复杂度：O(1)。我们只需要常数的空间存放若干变量
// 时间复杂度：O(n+m)，其中 n 和 m 分别为两个链表的长度。因为每次循环迭代中，l1 和 l2 只有一个元素会被放进合并链表中， 因此 while 循环的次数不会超过两个链表的长度之和。所有其他操作的时间复杂度都是常数级别的，因此总的时间复杂度为 O(n+m)。
var mergeTwoLists = function(list1, list2) {
    // 递归结束条件，当一个链表为null时，直接返回另一个
    if(!list1){
        return list2
    }
    if(!list2){
        return list1
    }
    // 如果 list1 链表当前节点值小于 list2.val
    if(list1.val<=list2.val){
        // 则将 list1的下一个指向 list2,list2 的下一个指向 list1.next
        list1.next = mergeTwoLists(list2,list1.next);
        //  最终返回 list1
        return list1;
    }else{
         // 如果 list2 链表当前节点值小于 list1.val
         // 则将 list2的下一个指向 list1,list1 的下一个指向 list2.next
        list2.next = mergeTwoLists(list1,list2.next);
         //  最终返回 list2
        return list2;
    }
};