两数相加 (opens new window)

• 难度：Medium
• 标签：链表

刷题思路

• [x] 链表推进,存入新链表
• [x] 链表推进,更新其中一个链表的值（不推荐）

方法 1 链表推进,存入新链表

• 复杂度：
  • 时间 O(max(l1,l2)). 入参较长者的长度.
  • 空间 O(1). 常数级空间.
• 结果:
  • 执行用时：140 ms, 在所有 JavaScript 提交中击败了 46.00%的用户
  • 内存消耗：42.6 MB, 在所有 JavaScript 提交中击败了 23.00 %的用户

var addTwoNumbers = function(l1, l2) {
    let carry = 0
    const head = new ListNode(null)
    let curr = head
    while (l1 || l2 || carry) {
        const sum = (l1?l1.val:0) + (l2?l2.val:0) + carry
        carry = sum > 9 ? 1 : 0
        curr.next = new ListNode(sum % 10)
        curr = curr.next
        if (l1) l1 = l1.next
        if (l2) l2 = l2.next
    }
    return head.next
};

方法 2 链表推进,更新其中一个链表的值

• 复杂度：
  • 时间 O(max(l1,l2)). 入参较长者的长度.
  • 空间 O(1). 常数级空间.
• 结果:
  • 执行用时：136 ms, 在所有 JavaScript 提交中击败了 76.11%的用户
  • 内存消耗：42.7 MB, 在所有 JavaScript 提交中击败了 23.46 %的用户

var addTwoNumbers = function(l1, l2) {
    let carry = 0
    const head = new ListNode(null)
    head.next = l1
    let prev = head
    while (prev.next || l2 || carry) {
        const sum = (prev.next?prev.next.val:0) + (l2?l2.val:0) + carry
        carry = sum > 9 ? 1 : 0
        // 如果 prev.next 本轮已经不存在则创建新对象，存在则直接更新val即可
        if (prev.next) {
            prev.next.val = sum % 10
        } else {
            prev.next = new ListNode(sum % 10)
        }
        prev = prev.next
        if (l2) l2 = l2.next
    }
    return head.next
};

其他

• 转换成对应的数字直接相加 (opens new window)

  • 令人惊叹的解法: JSON.stringify转字符串 => 正则提取数字 => 大数相加后 reduce 创建链表, JS 熟练度爆棚.

JS刷题记录 Leetcode-js (opens new window) 每周都会更新刷题心得或者题解, 你的点赞或 star 都将助力我产出更好内容~