devpoint.cn

链表相加是指将两个链表表示的数相加，得到一个新的链表表示的结果。假设两个链表的每个节点都表示一位数字，且是逆序存储的（即链表的尾部表示数字的最高位），那么可以按照以下步骤来实现链表相加：

1. 定义一个 ListNode 类来表示链表的节点，其中包含一个 val 属性表示节点的值，以及一个 next 属性表示指向下一个节点的指针。
2. 定义一个 addTwoNumbers 函数，接收两个链表作为参数。
3. 创建一个新链表 result，表示相加的结果。同时定义两个指针 p 和 q 分别指向两个链表的头节点，以及一个指针 curr 指向结果链表的头节点。
4. 对于每一位数字，将 p 和 q 指向的节点的值相加，并加上前一位数字的进位值，得到一个新的进位值和相加后的值。将该值存储到结果链表中，并将指针 p、q 和 curr 向后移动。
5. 如果有任何一个链表已经到达了末尾，则在计算下一位数字时只考虑另一个链表的值，并将前一位的进位值加到结果中。如果计算完所有位数后，前一位仍然有进位，则需要将进位值添加到结果链表的末尾。

下面是具体的实现代码：

class ListNode {
    constructor(val, next = null) {
        this.val = val;
        this.next = next;
    }
}

function addTwoNumbers(l1, l2) {
    let p = l1;
    let q = l2;
    let carry = 0; // 进位值
    let result = new ListNode(0);
    let curr = result;

    while (p !== null || q !== null) {
        const x = p ? p.val : 0;
        const y = q ? q.val : 0;
        const sum = x + y + carry;
        carry = Math.floor(sum / 10);
        curr.next = new ListNode(sum % 10);
        curr = curr.next;
        if (p) p = p.next;
        if (q) q = q.next;
    }

    if (carry > 0) {
        curr.next = new ListNode(carry);
    }

    return result.next;
}

在上述代码中，首先定义了一个 ListNode 类来表示链表的节点。在 addTwoNumbers 函数中，初始化了两个指针 p 和 q 分别指向两个链表的头节点，同时初始化了一个进位值 carry 和结果链表 result。然后，循环遍历两个链表，计算每一位数字的相加结果，并将结果存储到结果链表中。最后，如果前一位数字有进位，则需要将进位值添加到结果链表的末尾。

可以使用上述代码的时间复杂度是 $O(\max(m,n))$，其中 $m$ 和 $n$ 分别是两个链表的长度。这是因为需要遍历两个链表，并对每一位数字进行相加。空间复杂度也是 $O(\max(m,n))$，因为需要创建一个新的链表来存储相加的结果。

下面是一个示例，演示如何使用上述代码来计算链表相加：

const l1 = new ListNode(3, new ListNode(4, new ListNode(3)));
const l2 = new ListNode(5, new ListNode(6, new ListNode(4)));
const result = addTwoNumbers(l1, l2);
console.log(result);

上述示例中输出的结果为：

ListNode {
  val: 8,
  next: ListNode { val: 0, next: ListNode { val: 8, next: null } }
}