题目描述 21.合并两个有序链表

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

示例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 均按 非递减顺序 排列

思路

我们可以用两个指针分别遍历两个链表。

1. 当链表节点都不为空的时候，比较两个节点的值，找出最小的那个节点添加到新的需要返回的链表中
2. 当其中一个节点为空的时候，直接把另一个节点添加到需返回的链表中。

代码实现

1. 需要新建一个链表，空间复杂度

/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var mergeTwoLists = function(l1, l2) {
    let res = new ListNode()
    let cur = res
    while(l1 || l2) {
        let val1 = l1 ? l1.val : Number.MAX_SAFE_INTEGER
        let val2 = l2 ? l2.val : Number.MAX_SAFE_INTEGER
        let min
        if(val1 > val2) {
            min = val2
            l2 = l2.next
        }else {
            min = val1
            l1 = l1.next
        }
        cur.next = new ListNode(min)
        cur = cur.next
    }
    return res.next
}

2.不需要新建一个链表，空间复杂度

/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var mergeTwoLists = function (l1, l2) {
    let res = new ListNode()
    let cur = res
    while (l1 || l2) {
        let val1 = l1 ? l1.val : Number.MAX_SAFE_INTEGER
        let val2 = l2 ? l2.val : Number.MAX_SAFE_INTEGER
        let min
        if (val1 > val2) {
            cur.next = l2
            l2 = l2.next
        } else {
            cur.next = l1
            l1 = l1.next
        }
        cur = cur.next
    }
    return res.next
}

结尾

如果需要在本地测试代码的话，可以写一些辅助类和函数来帮助检查输入输出，我们可以自己定义ListNode类以及辅助函数arrayToList()方法将数组转换为链表，以及输出链表listToString()方法。完整代码如下

class ListNode {
    constructor(val, next) {
        this.val = val ? val : 0
        this.next = next ? null : next
    }
}

/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var mergeTwoLists = function (l1, l2) {
    let res = new ListNode()
    let cur = res
    while (l1 || l2) {
        let val1 = l1 ? l1.val : Number.MAX_SAFE_INTEGER
        let val2 = l2 ? l2.val : Number.MAX_SAFE_INTEGER
        let min
        if (val1 > val2) {
            cur.next = l2
            l2 = l2.next
        } else {
            cur.next = l1
            l1 = l1.next
        }
        cur = cur.next
    }
    return res.next
}

/**
 *
 * @param {ListNode} l
 */
function listToString(l) {
    let res = '['
    while (l) {
        res += l.val + ', '
        l = l.next
    }
    res += ']'
    return res
}

function arrayToList(arr) {
    let res = new ListNode(-1)
    let cur = res
    for (let item of arr) {
        let node = new ListNode(item)
        cur.next = node
        cur = cur.next
    }
    return res.next
}

const l1 = arrayToList([1, 2, 3])
const l2 = arrayToList([1, 2, 5, 6, 7])
const l = mergeTwoLists(l1, l2)
console.log(listToString(l))