题目描述

给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。

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

提示：

• 链表的长度范围为 [1, 100]
• 0 <= node.val <= 9
• 输入数据保证链表代表的数字无前导 0

测试用例

用例1

• 输入：l1 = [7,2,4,3], l2 = [5,6,4]
• 输出：[7,8,0,7]

用例2

• 输入：l1 = [2,4,3], l2 = [5,6,4]
• 输出：[8,0,7]

代码实现

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

function ListNode(val, next) {
  this.val = val === undefined ? 0 : val;
  this.next = next === undefined ? null : next;
}
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */

// 输入

var __readline = require("readline-sync");
__readline.setDefaultOptions({ prompt: "" });
var readline = __readline.prompt;

// 请输入l1
console.log("请输入l1: ");
const l1 = readline().split(",").map(Number);
const head1 = new ListNode(-1);
var cur = head1;
for (let i = 0; i < l1.length; i++) {
  cur.next = new ListNode(l1[i]);
  cur = cur.next;
}

console.log("请输入l2: ");
const l2 = readline().split(",").map(Number);
const head2 = new ListNode(-1);
cur = head2;
for (let i = 0; i < l2.length; i++) {
  cur.next = new ListNode(l2[i]);
  cur = cur.next;
}

var addTwoNumbers = function (l1, l2) {
  // 翻转 + 头插
  let cur1 = l1;
  let pre1 = null;
  while (cur1) {
    let temp = cur1.next;
    cur1.next = pre1;
    pre1 = cur1;
    cur1 = temp;
  }
  // pre1此时指向头结点
  l1 = pre1;
  let cur2 = l2;
  let pre2 = null;
  while (cur2) {
    let temp = cur2.next;
    cur2.next = pre2;
    pre2 = cur2;
    cur2 = temp;
  }
  // pre2此时指向头结点
  l2 = pre2;

  // 开始相加，并头插
  let prev = null;
  // 进位
  let add = 0;
  while (l1 || l2) {
    let val1 = l1 ? l1.val : 0;
    let val2 = l2 ? l2.val : 0;
    let sum = val1 + val2 + add;
    add = Math.floor(sum / 10);

    sum %= 10;
    // 头插
    const cur = new ListNode(sum);
    cur.next = prev;
    prev = cur;

    // 遍历
    l1 = l1?.next;
    l2 = l2?.next;
  }
  // 最后一个如果还有进位就继续头插
  if (add) {
    const cur = new ListNode(sum);
    cur.next = prev;
    prev = cur;
  }
  return prev;
};

let res = addTwoNumbers(head1.next, head2.next);

let arr = [];
while (res) {
  arr.push(res.val);
  res = res.next;
}
console.log("结果为: ", arr);

/* 
  请输入l1:
  7,2,4,3
  请输入l2:
  5,6,4
  结果为:  [ 7, 8, 0, 7 ]
*/