# 0445. 两数相加 II

### 题目地址(445. 两数相加 II)

<https://leetcode-cn.com/problems/add-two-numbers-ii/>

### 题目描述

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

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

 

进阶：

如果输入链表不能修改该如何处理？换句话说，你不能对列表中的节点进行翻转。

 

示例：

输入：(7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 8 -> 0 -> 7

```

### 前置知识

* 链表
* 栈

### 公司

* 腾讯
* 百度
* 字节

### 思路

由于需要从低位开始加，然后进位。 因此可以采用栈来简化操作。 依次将两个链表的值分别入栈 stack1 和 stack2，然后相加入栈 stack，进位操作用一个变量 carried 记录即可。

最后根据 stack 生成最终的链表即可。

> 也可以先将两个链表逆置，然后相加，最后将结果再次逆置。

### 关键点解析

* 栈的基本操作
* carried 变量记录进位
* 循环的终止条件设置成`stack.length > 0` 可以简化操作
* 注意特殊情况， 比如 1 + 99 = 100

### 代码

* 语言支持：JS，C++, Python3

JavaScript Code:

```js
/*
 * @lc app=leetcode id=445 lang=javascript
 *
 * [445] Add Two Numbers II
 */
/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var addTwoNumbers = function (l1, l2) {
  const stack1 = [];
  const stack2 = [];
  const stack = [];

  let cur1 = l1;
  let cur2 = l2;
  let curried = 0;

  while (cur1) {
    stack1.push(cur1.val);
    cur1 = cur1.next;
  }

  while (cur2) {
    stack2.push(cur2.val);
    cur2 = cur2.next;
  }

  let a = null;
  let b = null;

  while (stack1.length > 0 || stack2.length > 0) {
    a = Number(stack1.pop()) || 0;
    b = Number(stack2.pop()) || 0;

    stack.push((a + b + curried) % 10);

    if (a + b + curried >= 10) {
      curried = 1;
    } else {
      curried = 0;
    }
  }

  if (curried === 1) {
    stack.push(1);
  }

  const dummy = {};

  let current = dummy;

  while (stack.length > 0) {
    current.next = {
      val: stack.pop(),
      next: null,
    };

    current = current.next;
  }

  return dummy.next;
};
```

C++ Code：

```
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        auto carry = 0;
        auto ret = (ListNode*)nullptr;
        auto s1 = vector<int>();
        toStack(l1, s1);
        auto s2 = vector<int>();
        toStack(l2, s2);
        while (!s1.empty() || !s2.empty() || carry != 0) {
            auto v1 = 0;
            auto v2 = 0;
            if (!s1.empty()) {
                v1 = s1.back();
                s1.pop_back();
            }
            if (!s2.empty()) {
                v2 = s2.back();
                s2.pop_back();
            }
            auto v = v1 + v2 + carry;
            carry = v / 10;
            auto tmp = new ListNode(v % 10);
            tmp->next = ret;
            ret = tmp;
        }
        return ret;
    }
private:
    // 此处若返回而非传入vector，跑完所有测试用例多花8ms
    void toStack(const ListNode* l, vector<int>& ret) {
        while (l != nullptr) {
            ret.push_back(l->val);
            l = l->next;
        }
    }
};

// 逆置，相加，再逆置。跑完所有测试用例比第一种解法少花4ms
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        auto rl1 = reverseList(l1);
        auto rl2 = reverseList(l2);
        auto ret = add(rl1, rl2);
        return reverseList(ret);
    }
private:
    ListNode* reverseList(ListNode* head) {
        ListNode* prev = NULL;
        ListNode* cur = head;
        ListNode* next = NULL;
        while (cur != NULL) {
            next = cur->next;
            cur->next = prev;
            prev = cur;
            cur = next;
        }
        return prev;
    }

    ListNode* add(ListNode* l1, ListNode* l2) {
        ListNode* ret = nullptr;
        ListNode* cur = nullptr;
        int carry = 0;
        while (l1 != nullptr || l2 != nullptr || carry != 0) {
            carry += (l1 == nullptr ? 0 : l1->val) + (l2 == nullptr ? 0 : l2->val);
            auto temp = new ListNode(carry % 10);
            carry /= 10;
            if (ret == nullptr) {
                ret = temp;
                cur = ret;
            }
            else {
                cur->next = temp;
                cur = cur->next;
            }
            l1 = l1 == nullptr ? nullptr : l1->next;
            l2 = l2 == nullptr ? nullptr : l2->next;
        }
        return ret;
    }
};
```

Python Code:

```python
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        def listToStack(l: ListNode) -> list:
            stack, c = [], l
            while c:
                stack.append(c.val)
                c = c.next
            return stack

        # transfer l1 and l2 into stacks
        stack1, stack2 = listToStack(l1), listToStack(l2)

        # add stack1 and stack2
        diff = abs(len(stack1) - len(stack2))
        stack1 = ([0]*diff + stack1 if len(stack1) < len(stack2) else stack1)
        stack2 = ([0]*diff + stack2 if len(stack2) < len(stack1) else stack2)
        stack3 = [x + y for x, y in zip(stack1, stack2)]

        # calculate carry for each item in stack3 and add one to the item before it
        carry = 0
        for i, val in enumerate(stack3[::-1]):
            index = len(stack3) - i - 1
            carry, stack3[index] = divmod(val + carry, 10)
            if carry and index == 0:
                stack3 = [1] + stack3
            elif carry:
                stack3[index - 1] += 1

        # transfer stack3 to a linkedList
        result = ListNode(0)
        c = result
        for item in stack3:
            c.next = ListNode(item)
            c = c.next

        return result.next
```

**复杂度分析**

其中 M 和 N 分别为两个链表的长度。

* 时间复杂度：$O(M + N)$
* 空间复杂度：$O(M + N)$

大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库：<https://github.com/azl397985856/leetcode> 。 目前已经 37K star 啦。 大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。 ![](https://p.ipic.vip/f0dl5y.jpg)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/medium/445.add-two-numbers-ii.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.