445. Add Two Numbers II

445. Add Two Numbers IIopen in new window

🟠 🔖 栈 链表 数学 🔗 LeetCodeopen in new window

题目

You are given two non-empty linked lists representing two non-negative integers. The most significant digit comes first and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example 1:

Input: l1 = [7,2,4,3], l2 = [5,6,4]
Output: [7,8,0,7]

Example 2:

Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [8,0,7]

Example 3:

Input: l1 = [0], l2 = [0]
Output: [0]

Constraints:

The number of nodes in each linked list is in the range [1, 100].
0 <= Node.val <= 9
It is guaranteed that the list represents a number that does not have leading zeros.

Follow up: Could you solve it without reversing the input lists?

题目大意

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

解题思路

这道题是第 2 题的变种题，第 2 题中的 2 个数是从个位逆序排到高位，这样相加只用从头加到尾，进位一直进位即可。

这道题的主要难点在于链表中数位的顺序与我们做加法的顺序是相反的，而且要求不能反转链表，为了逆序处理所有数位，我们可以使用栈：把所有数字压入栈中，再依次取出相加。计算过程中需要注意进位的情况。

代码

/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var addTwoNumbers = function (l1, l2) {
  const linkToStack = (head) => {
    let stack = [];
    while (head) {
      stack.push(head.val);
      head = head.next;
    }
    return stack;
  };

  let stack1 = linkToStack(l1);
  let stack2 = linkToStack(l2);
  let res = null;
  let carry = 0;
  while (stack1.length !== 0 || stack2.length !== 0 || carry !== 0) {
    let sum = carry;
    if (stack1.length !== 0) {
      sum += stack1.pop();
    }
    if (stack2.length !== 0) {
      sum += stack2.pop();
    }
    carry = Math.floor(sum / 10);
    sum %= 10;
    const node = new ListNode(sum, res);
    res = node;
  }

  return res;
};

445. Add Two Numbers II

# 445. Add Two Numbers IIopen in new window

# 题目

# 题目大意

# 解题思路

# 代码

# 相关题目

445. Add Two Numbers IIopen in new window

题目

题目大意

解题思路

代码

相关题目