2.两数相加

思路

新建一个链表，遍历两个链表来模拟相加的操作，然后把数字追加到新的链表中

按照如上思路，可以得出如下代码

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */

class ListNode {
    val: number
    next: ListNode | null

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

function addTwoNumbers(
    l1: ListNode | null,
    l2: ListNode | null
): ListNode | null {
    // 新建一个链表
    const l3 = new ListNode()

    // 初始化节点
    let p1 = l1
    let p2 = l2
    let p3 = l3

    // 开始遍历两条链表的循环
    while (p1 || p2) {
        // 兼容一下如果两条链表的长度不一样的情况，没有就为0
        const v1 = p1?.val || 0
        const v2 = p2?.val || 0
        const val = v1 + v2

        // 追加数据到新链表的下一个节点
        p3.next = new ListNode(val)

        // 计算数据完成，把 p1 和 p2 移动到下一个节点
        // 兼容一下节点有可能没有的情况
        if (p1) {
            p1 = p1.next
        }

        if (p2) {
            p2 = p2.next
        }

        // 这里可以忽略，因为 p3 所在的链表在上面有初始化 `l3 = new ListNode()`,所以 p3 是肯定有数据的
        // if (p3) {
        //     p3 = p3.next
        // }
        p3 = p3.next
    }

    return l3.next
}

如上代码执行的话，通过 leetcode 的测试用例

input: [2, 4, 3][(5, 6, 4)]
output: [7, 10, 7]
expect: [7, 0, 8]

不对的原因是没有十位数进一位

需要一个临时变量存储十位数进一位的那个数，然后再进算总和的时候再加上去,综上所述得出如下代码

function addTwoNumbers(
    l1: ListNode | null,
    l2: ListNode | null
): ListNode | null {
    // 新建一个链表
    const l3 = new ListNode()

    // 初始化节点
    let p1 = l1
    let p2 = l2
    let p3 = l3

    let carry = 0
    // 开始遍历两条链表的循环
    while (p1 || p2) {
        // 兼容一下如果两条链表的长度不一样的情况，没有就为0
        const v1 = p1?.val || 0
        const v2 = p2?.val || 0

        // 下一次遍历的时候，需要加上上一轮存储的进位
        const val = v1 + v2 + carry

        // 获取十位数的进位
        carry = Math.floor(val / 10)

        // 追加数据到新链表的下一个节点
        p3.next = new ListNode(val % 10)

        // 计算数据完成，把 p1 和 p2 移动到下一个节点
        // 兼容一下节点有可能没有的情况
        if (p1) {
            p1 = p1.next
        }

        if (p2) {
            p2 = p2.next
        }

        // 这里可以忽略，因为 p3 所在的链表在上面有初始化 `l3 = new ListNode()`,所以 p3 是肯定有数据的
        // if (p3) {
        //     p3 = p3.next
        // }
        p3 = p3.next
    }

    if (carry) {
        p3.next = new ListNode(carry)
    }

    return l3.next
}

复杂度分析

时间复杂度: O(N), 也就是 p1 或者是 p2 长度最长的那位进行 while 循环

空间复杂度: O(N)，因为定义了一个链表，链表的长度可能就是 p1 或者是 p2 的长度最长的那个链表，如果有个位数相加超过 10 的情况下, 有可能就是 O(N) + 1 , 省略后得到 O(N)