菜园前端

Appearance

2. 两数相加 ​

原文题目

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

https://leetcode.cn/problems/add-two-numbers

题目分析 ​

题目中的意思就是，例如有两组数字，分别是 201 和 19 ，那么他们相加的结果就是 220 ，但是这两组数字是以链表的形式存储的，也就是说，我们需要将这两个链表进行相加，然后返回一个新的链表。

链表数据是以相反的顺序存储，链表的形式如下：

第一组链表：1 -> 0 -> 2

第二组链表：9 -> 1

相加的链表：0 -> 2 -> 2

js
const l1 = { val: 1, next: { val: 0, next: { val: 2, next: null } } }
const l2 = { val: 9, next: { val: 1, next: null } }
const l1 = { val: 1, next: { val: 0, next: { val: 2, next: null } } }
const l2 = { val: 9, next: { val: 1, next: null } }

题解思路 ​

方式一：转成数字相加 ​

最简单的方式，把两个链表转成数字 201 和 19 进行相加，得出 220 再将其转为链表 0 -> 2 -> 2

js
const addTwoNumbers = function (l1, l2) {
    const a1 = [] // [3, 4, 2]
    const a2 = [] // [4, 6, 5]

    while (l1 || l2) {
        if (l1) {
            a1.unshift(l1.val)
            l1 = l1.next
        }

        if (l2) {
            a2.unshift(l2.val)
            l2 = l2.next
        }
    }

    const n1 = a1.join('') // 342
    const n2 = a2.join('') // 465
    const n3 = String(Number(n1) + Number(n2)) // '807'

    let head = { next: null }
    let current = head

    for (let index = n3.length - 1; index >= 0; index--) {
        const node = { val: Number(n3[index]), next: null }

        current.next = node
        current = current.next
    }

    return head.next
}

let l1 = { val: 1, next: { val: 0, next: { val: 2, next: null } } }
let l2 = { val: 9, next: { val: 1, next: null } }

addTwoNumbers(l1, l2)
const addTwoNumbers = function (l1, l2) {
    const a1 = [] // [3, 4, 2]
    const a2 = [] // [4, 6, 5]

    while (l1 || l2) {
        if (l1) {
            a1.unshift(l1.val)
            l1 = l1.next
        }

        if (l2) {
            a2.unshift(l2.val)
            l2 = l2.next
        }
    }

    const n1 = a1.join('') // 342
    const n2 = a2.join('') // 465
    const n3 = String(Number(n1) + Number(n2)) // '807'

    let head = { next: null }
    let current = head

    for (let index = n3.length - 1; index >= 0; index--) {
        const node = { val: Number(n3[index]), next: null }

        current.next = node
        current = current.next
    }

    return head.next
}

let l1 = { val: 1, next: { val: 0, next: { val: 2, next: null } } }
let l2 = { val: 9, next: { val: 1, next: null } }

addTwoNumbers(l1, l2)

时间复杂度：O(2n)

空间复杂度：O(2n)

代码分析
  1. 首先通过 while 遍历两个链表，结合 unshift 方法将其转为正序的数组。
js
while (l1 || l2) {
    if (l1) {
        a1.unshift(l1.val)
        l1 = l1.next
    }

    if (l2) {
        a2.unshift(l2.val)
        l2 = l2.next
    }
}
while (l1 || l2) {
    if (l1) {
        a1.unshift(l1.val)
        l1 = l1.next
    }

    if (l2) {
        a2.unshift(l2.val)
        l2 = l2.next
    }
}
  1. 通过 join 将数组再次转成数字，并进行相加，得出 807
js
const n1 = a1.join('') // 342
const n2 = a2.join('') // 465
const n3 = String(Number(n1) + Number(n2)) // '807'
const n1 = a1.join('') // 342
const n2 = a2.join('') // 465
const n3 = String(Number(n1) + Number(n2)) // '807'
  1. 最后将 807 转为反序链表即可，首先通过 for 生成三组反序的 node 节点
js
for (let index = n3.length - 1; index >= 0; index--) {
    const node = { val: Number(n3[index]), next: null }
}
for (let index = n3.length - 1; index >= 0; index--) {
    const node = { val: Number(n3[index]), next: null }
}
  1. 通过对象指针的思路，将三组 node 节点依次赋值给 next
js
let head = { next: null }
let current = head

for (let index = n3.length - 1; index >= 0; index--) {
    current.next = node
    current = current.next
}
let head = { next: null }
let current = head

for (let index = n3.length - 1; index >= 0; index--) {
    current.next = node
    current = current.next
}
  1. 返回 head 的 next 属性
js
return head.next
return head.next

方式二：个位数相加，10 进位 ​

按照正常的数学方式，就是直接 201 + 19 = 220，但是我们的数据是逆向存储的，所以转成数字相加在转回链表的复杂度会更高。所以可以通过从个位数相加，大于 10 就进位，这样一次遍历就可以完成。

个位数：1 + 9 = 0，因为进位 1 所以十位数额外 +1

十位数：0 + 1 + 1 = 2，没有进位

百位数：2 + 0 = 2

最终得出结果刚好是 022，在一次遍历的过程中，可直接将 022 依次存储到链表中。

js
const addTwoNumbers = function (l1, l2) {
    let head = { next: null }
    let current = head
    let carry = 0 // 是否进位

    // 依次是个位数、十位数、百位数...、carry 位数
    while (l1 || l2 || carry) {
        let sum = carry

        if (l1) {
            sum += l1.val
            l1 = l1.next
        }

        if (l2) {
            sum += l2.val
            l2 = l2.next
        }

        current.next = { val: sum % 10, next: null }
        current = current.next
        carry = Math.floor(sum / 10)
    }

    return head.next
}

let l1 = { val: 1, next: { val: 0, next: { val: 2, next: null } } }
let l2 = { val: 9, next: { val: 1, next: null } }

addTwoNumbers(l1, l2)
const addTwoNumbers = function (l1, l2) {
    let head = { next: null }
    let current = head
    let carry = 0 // 是否进位

    // 依次是个位数、十位数、百位数...、carry 位数
    while (l1 || l2 || carry) {
        let sum = carry

        if (l1) {
            sum += l1.val
            l1 = l1.next
        }

        if (l2) {
            sum += l2.val
            l2 = l2.next
        }

        current.next = { val: sum % 10, next: null }
        current = current.next
        carry = Math.floor(sum / 10)
    }

    return head.next
}

let l1 = { val: 1, next: { val: 0, next: { val: 2, next: null } } }
let l2 = { val: 9, next: { val: 1, next: null } }

addTwoNumbers(l1, l2)

时间复杂度：O(n)

空间复杂度：O(n)

代码分析
  1. 首页还是通过 while 遍历两个链表的个位数、十位数、百位数...
js
while (l1 || l2) {}
while (l1 || l2) {}
  1. while 循环第一次进来是个位数相加、第二次是十位数相加、第三次是百位数相加，以此类推。例如链表 l1 的个位数是 1 和链表 l2 的个位数 9 进行相加。
js
while (l1 || l2) {
    let sum = 0

    if (l1) {
        sum += l1.val
        l1 = l1.next
    }

    if (l2) {
        sum += l2.val
        l2 = l2.next
    }
}
while (l1 || l2) {
    let sum = 0

    if (l1) {
        sum += l1.val
        l1 = l1.next
    }

    if (l2) {
        sum += l2.val
        l2 = l2.next
    }
}
  1. 如果两个数相加大于等于 10，则需要进位，并且记录起来。例如个位数相加 1 + 9 = 10 ，个位数的值是 0 ，百位数的值要加上进位的 1
js
while (l1 || l2) {
    let sum = carry // 例如百位数进来的时候，就自动在总和中 +1 了

    current.next = { val: sum % 10, next: null } // 存储当前相加的结果
    current = current.next
    carry = Math.floor(sum / 10) // 计算当前总和 sum 是否达到进位标准
}
while (l1 || l2) {
    let sum = carry // 例如百位数进来的时候，就自动在总和中 +1 了

    current.next = { val: sum % 10, next: null } // 存储当前相加的结果
    current = current.next
    carry = Math.floor(sum / 10) // 计算当前总和 sum 是否达到进位标准
}
  1. 最后的位数相加如果大于 10 ，需要多进入 while 循环一次。例如我重新定义一个新的链表 2 和链表 8 ，他们只有个位数，没有十位数。按照上方的思路 while 循环只会进入一次，因为第二次进入的时候 l1 和 l2 都是 null，这就导致了个位数的结果是 0 程序就结束了。正确的方式是十位数应该要是 1 的。
js
while (l1 || l2 || carry) {}
while (l1 || l2 || carry) {}

所以 while 循环要加上 carry 判断条件，如果 carry 有值，按照新的举例来说，它的身份就是十位数。

更新时间: