怎样用 JavaScript 实现链表相加

链表相加是指给定两个代表非负整数的链表，其中每个节点分别包含一个数位，数字以逆序方式存储，即个位存储于链表的头部，其余高位依次存储于链表中，并要求返回一个新的链表来表示两数的和。链表相加的核心步骤包括：创建新链表、遍历链表、求和以及处理进位。在详细描述中，我们可以关注链表遍历时的数位相加以及进位处理，这需要通过循环对每个数位进行操作，若两链表长度不同，则考虑短链表遍历结束后如何处理剩余的数位，并确保进位信息不丢失。

一、链表定义与初始化

链表是一种常见的基础数据结构，在JavaScript中通常通过对象来实现链表的节点。链表节点包括两个属性：存储的值(val)以及指向下一个节点的引用(next)。

function ListNode(val, next) {

    this.val = (val === undefined ? 0 : val);
    this.next = (next === undefined ? null : next);
}
// 初始化链表
function createLinkedList(array) {
    let head = new ListNode(0);
    let current = head;
    array.forEach((val) => {
        current.next = new ListNode(val);
        current = current.next;
    });
    return head.next;
}

二、链表遍历与求和

实现链表相加主要涉及对两个链表的逐节点遍历和求和。在遍历时，需要同时从两个链表的头部开始，分别提取节点的值进行相加。若某个链表已经遍历完成，应将其剩余部分视为0。

// 链表求和函数

function addTwoNumbers(l1, l2) {
    let head = new ListNode(0);
    let current = head;
    let carry = 0; // 进位初始化为0
    while (l1 !== null || l2 !== null) {
        let sum = carry;
        if (l1 !== null) {
            sum += l1.val;
            l1 = l1.next;
        }
        if (l2 !== null) {
            sum += l2.val;
            l2 = l2.next;
        }
        carry = Math.floor(sum / 10); // 更新进位
        current.next = new ListNode(sum % 10); // 创建新节点存储个位数
        current = current.next;
    }
    // 若最终仍有进位，需要添加额外节点
    if (carry > 0) {
        current.next = new ListNode(carry);
    }
    return head.next;
}

三、进位处理

在链表相加的过程中，进位是一个需要重点处理的问题。每当两个数字相加超过10时，应将超过部分转化为进位，只将个位数作为新节点加入到结果链表中。遍历完成后，若还存在进位，需将进位作为新节点添加到链表末尾。

// 考虑进位的处理逻辑，在上述addTwoNumbers函数中已经包含

while (l1 !== null || l2 !== null) {
    let sum = carry; // 考虑上一轮的进位
    // 遍历链表和求和
}
// 遍历完成后检查进位
if (carry > 0) {
    current.next = new ListNode(carry); // 额外节点包含进位值
}

四、测试用例和功能验证

在实现了链表相加的函数后，需要通过测试用例来验证功能的正确性。编写多个测试用例，覆盖正常和边界情况，确保链表相加无误，并正确处理了进位情况。

// 测试用例

function testAddTwoNumbers() {
    let list1 = createLinkedList([2, 4, 3]);
    let list2 = createLinkedList([5, 6, 4]);
    let sumList = addTwoNumbers(list1, list2);
    printLinkedList(sumList); // 应输出7 -> 0 -> 8，表示数字807
    let list3 = createLinkedList([0]);
    let list4 = createLinkedList([0]);
    sumList = addTwoNumbers(list3, list4);
    printLinkedList(sumList); // 应输出0
    let list5 = createLinkedList([9,9,9,9,9,9,9]);
    let list6 = createLinkedList([9,9,9,9]);
    sumList = addTwoNumbers(list5, list6);
    printLinkedList(sumList); // 应输出8,9,9,9,0,0,0,1
    // ...更多测试用例
}
// 打印链表函数
function printLinkedList(list) {
    let output = '';
    while (list !== null) {
        output += list.val + ' -> ';
        list = list.next;
    }
    console.log(output.slice(0, -4)); // 去掉末尾多余的箭头
}
testAddTwoNumbers();

通过仔细编写测试用例并进行功能验证，我们可确信链表相加函数的可靠性和准确性。以上四部分构成实现链表相加逻辑的完整代码和描述，对于任意长度和内容的链表求和问题，该实现都能得到正确的结果。

相关问答FAQs：

1. 链表相加的基本原理是什么？

链表相加是一种常见的编程问题，通常用于解决两个链表中存储的数字相加的情况。基本原理是将两个链表的对应节点进行相加，然后将结果存储在一个新的链表中。如果两个链表的长度不同，可以用零来填补短链表的空缺。

2. 如何用 JavaScript 实现链表相加？

要用 JavaScript 实现链表相加，首先需要定义链表节点的数据结构。可以使用一个对象来表示每个节点，该对象包含两个属性：value（节点的值）和next（指向下一个节点的指针）。

然后，创建两个链表，并确保它们的节点数量相同。逐个遍历两个链表的节点，将对应节点的值相加，并将结果存储在新链表的节点中。如果有进位产生，需要将进位加到下一个节点上。

最后，如果遍历完两个链表后仍有进位，需要添加一个额外的节点来存储进位。

3. 有没有其他方法可以用 JavaScript 实现链表相加？

除了上述基本方法外，还有一种更优化的方法可以用 JavaScript 实现链表相加，即将链表转化为字符串，然后将字符串转化为数字进行相加，最后再将结果转化为链表。

这种方法的好处是避免了手动处理进位的逻辑，简化了代码的实现。但需要注意的是，当链表的长度非常长时，转化为数字可能会导致溢出的问题，因此需要进行相应的处理。