660ff0c Jul 9, 2019
1 contributor

### Users who have contributed to this file

184 lines (157 sloc) 5.3 KB

## 题目描述

``````You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

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

Example

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.

``````

## 关键点解析

1. 链表这种数据结构的特点和使用

2. 用一个carried变量来实现进位的功能，每次相加之后计算carried，并用于下一位的计算

## 代码

• 语言支持：JS，C++

JavaScript:

```/**
* function ListNode(val) {
*     this.val = val;
*     this.next = null;
* }
*/
/**
* @param {ListNode} l1
* @param {ListNode} l2
* @return {ListNode}
*/
var addTwoNumbers = function(l1, l2) {
var carried = 0; // 用于进位
const noop = {
val: 0,
next: null
};
let currentL1 = l1;
let currentL2 = l2;
let currentNode = head; // 返回的链表的当前node
let newNode; // 声明在外面节省内存
let previousNode; // 记录前一个节点，便于删除最后一个节点

while (currentL1 || currentL2) {
newNode = new ListNode(0);

currentNode.val =
((currentL1 || noop).val + (currentL2 || noop).val + carried) % 10;

currentNode.next = newNode;
previousNode = currentNode;
currentNode = newNode;

if ((currentL1 || noop).val + (currentL2 || noop).val + carried >= 10) {
carried = 1;
} else {
carried = 0;
}

currentL1 = (currentL1 || noop).next;
currentL2 = (currentL2 || noop).next;
}

if (carried) {
// 还有位没进呢
previousNode.next = new ListNode(carried)
} else {
previousNode.next = null;
}

};```

C++

C++代码与上面的JavaScript代码略有不同：将carry是否为0的判断放到了while循环中

```/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* addTwoNumbers(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;
}
};```

## 拓展

### 描述

1. 将两个链表的第一个节点值相加，结果转为0-10之间的个位数，并设置进位信息
2. 将两个链表第一个节点以后的链表做带进位的递归相加
3. 将第一步得到的头节点的next指向第二步返回的链表

### C++实现

```// 普通递归
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
}

private:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2, int carry) {
if (l1 == nullptr && l2 == nullptr && carry == 0) return nullptr;
carry += (l1 == nullptr ? 0 : l1->val) + (l2 == nullptr ? 0 : l2->val);
auto ret = new ListNode(carry % 10);
ret->next = addTwoNumbers(l1 == nullptr ? l1 : l1->next,
l2 == nullptr ? l2 : l2->next,
carry / 10);
return ret;
}
};
// （类似）尾递归
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
}

private:
void addTwoNumbers(ListNode*& head, ListNode* cur, ListNode* l1, ListNode* l2, int carry) {
if (l1 == nullptr && l2 == nullptr && carry == 0) return;
carry += (l1 == nullptr ? 0 : l1->val) + (l2 == nullptr ? 0 : l2->val);
auto temp = new ListNode(carry % 10);
if (cur == nullptr) {