两数相加的问题

题目是：给两个非空的链表，表示两个非负整数。它们每位数都是按照逆序的方式存储，并且每一个节点只能存储一位数字。现在两个数相加，并且以相同的形式返回一个表示和的链表。

首先回顾一下，什么是链表？链表是一种数据结构，由一系列的节点组成，每一个节点有两个部分：一部分是存储数据元素，一部分是存储下一个节点地址的指针。

在解答这个题目过程中还运用到进位，进位是一种运算形式，加法运算中，每一数位上的数相加满十，则用一个高位上的数记其和1。

既然是链表运算，就先定义一个链表节点的构造函数：

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

在运算的函数里面，首先要定义一个头节点：

let Head = new ListNode(0);

定义一个表示当前节点的变量：

let current = Head;

进位标志为：

let carry = 0;

遍历链表：

while (l1 !== null || l2 !== null) { // 当两个链表中任意一个不为空时继续循环let n1 = l1 === null ? 0 : l1.val; // 若l1为空，则取值为0let n2 = l2 === null ? 0 : l2.val; // 若l2为空，则取值为0let sum = n1 + n2 + carry; // 计算当前位和进位之和carry = Math.floor(sum / 10); // 计算新的进位current.next = new ListNode(sum % 10); // 创建新节点，并设置其值为和除以10的余数current = current.next; // 移动到下一个节点if (l1 !== null) l1 = l1.next; // 移动l1指针if (l2 !== null) l2 = l2.next; // 移动l2指针}

如果进位标志大于0，那就在链表后面添加一个新的节点：

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

最后返回链表。

完整代码如下：

class ListNode {constructor(val, next = null) {this.val = val;this.next = next;}
}/*** @param {ListNode} l1* @param {ListNode} l2* @return {ListNode}*/
var addTwoNumbers = function(l1, l2) {
let dummyHead = new ListNode(0); // 创建一个虚拟头节点let current = dummyHead; // 当前节点指针，初始指向虚拟头节点let carry = 0; // 进位标志while (l1 !== null || l2 !== null) { // 当两个链表中任意一个不为空时继续循环let n1 = l1 === null ? 0 : l1.val; // 若l1为空，则取值为0let n2 = l2 === null ? 0 : l2.val; // 若l2为空，则取值为0let sum = n1 + n2 + carry; // 计算当前位和进位之和carry = Math.floor(sum / 10); // 计算新的进位current.next = new ListNode(sum % 10); // 创建新节点，并设置其值为和除以10的余数current = current.next; // 移动到下一个节点if (l1 !== null) l1 = l1.next; // 移动l1指针if (l2 !== null) l2 = l2.next; // 移动l2指针}// 如果最后还有进位，则在链表末尾添加一个新的节点表示这个进位if (carry > 0) {current.next = new ListNode(carry);}return dummyHead.next;
};