本文关键词：两数相加，链表，求加法，题解，leetcode, 力扣，python, c++, java
题目地址：https://leetcode.com/problems/add-two-numbers-ii/description/
题目描述
Youare given two non-empty linked lists representing two non-negative integers. The most significant digit comes first and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.
Youmay assume the two numbers do not contain any leading zero, except the number 0 itself.
Follow up:
What if you cannot modify the input lists? In other words, reversing the lists is not allowed.
Example:
Input: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 8 -> 0 -> 7
题目大意
有两个链表，分别是正序的十进制数字。现在要求两个十位数字的和，要求返回的结果也是链表。
解题方法
前言
加法是我们上小学的时候开始学习的第一种数学运算。
在算法题中，「求加法」问题大多考察「列竖式」求和。
题目中，「两数之和」通常与其他形式表示的数字结合起来：
- 两个字符串形式的数字相加（第 415 题）
- 两个链表形式的数字相加（第 2 、445、369 题）
- 数组形式的数字相加（第 66 、989题）
- 两个二进制形式的数字相加（第 67 题）
做法都是非常类似的，本质是在考察各种数据表示形式：字符串，链表，数组，二进制。
我们只要掌握了用「列竖式」求「两数之和」的方法，这类题目全都可以秒杀。
十进制加法
我们先回顾一下十进制加法的计算过程：
使用「竖式」计算十进制的加法的方式：
1、 两个「加数」的右端对齐；
2、 从最右侧开始，从右向左依次计算对应的两位数字的和，如果有进位需要加上进位如果和大于等于10，则把和的个位数字计入结果，并向前面进位；
3、 重复步骤2；
4、 当两个「加数」的每个位置都计算完成，如果最后仍有进位，需要把进位数字保留到计算结果中；
在实现中需要注意的有：
1、 不可以把链表/字符串表示的「加数」先转化成int型数字再求和，因为可能溢出；
2、 两个「加数」的字符串长度可能不同；
3、 在最后，如果进位carry不为0，那么最后需要计算进位；
4、 注意结果数字是否为低位结果在前，根据题目要求判断最后是否要反转结果；
思路
本题中的两个链表表示的数字是个位在后，高位在前。与 [2. 两数相加open in new window][2. _open in new window] 中的链表正好相反。
因为加法需要从个位数开始相加，而链表的遍历是从头部（十进制的高位）开始的，因此我们需要把链表翻转过来。
那么就有了两种思路：
思路一：反转链表
思路二：使用栈保存链表中的数字。
栈是先进后出的，所以起到了翻转功能
题目中说了：不能修改输入的链表。所以只能用思路二「栈」来解决。
方法：栈 + 循环
步骤：
1、 先对两个链表分别遍历放到栈中；
2、 从栈中分别弹出栈顶数字adder1和adder2，计算adder1和adder2之和，再加上进位carry，得到当前位置的和sum；
1、 如果sum>=10，那么进位carry=1，当前位设置为sum-10；
2、 如果sum<10，那么进位carry=0，当前位设置为sum；
3、 设置新链表节点，其值为sum，逆序拼接成链表即可；
代码中的巧妙之处：
1、 while(!st1.empty()||!st2.empty()||carry>0)含义：
1、 栈1和栈2只要有一个没遍历完，那么就继续遍历；
2、 如果栈1和栈2都遍历完了，但是最后留下的进位carry!=0，那么需要把进位也保留到结果中；
2、 取栈顶元素的时候，如果栈1或栈2已经遍历完了（即st1.empty()或者st2.empty()），则认为当前的加数是0；
3、 逆序拼接链表的方法：先定义了一个哑结点dummy，然后每次把新构建的链表结点放到dummy和dummy->next之间，最后返回结果是dummy->next；
Java 代码如下：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
Stack<Integer> st1 = new Stack();
Stack<Integer> st2 = new Stack();
while (l1 != null) {
st1.push(l1.val);
l1 = l1.next;
}
while (l2 != null) {
st2.push(l2.val);
l2 = l2.next;
}
int carry = 0;
ListNode dummy = new ListNode(0);
while (!st1.empty() || !st2.empty() || carry > 0) {
int adder1 = st1.empty() ? 0 : st1.pop();
int adder2 = st2.empty() ? 0 : st2.pop();
int sum = adder1 + adder2 + carry;
carry = sum >= 10 ? 1 : 0;
sum = sum >= 10 ? sum - 10 : sum;
ListNode cur = new ListNode(sum);
cur.next = dummy.next;
dummy.next = cur;
}
return dummy.next;
}
}
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37
C++代码如下：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
stack<int> st1;
stack<int> st2;
while (l1) {
st1.push(l1->val);
l1 = l1->next;
}
while (l2) {
st2.push(l2->val);
l2 = l2->next;
}
int carry = 0;
ListNode* dummy = new ListNode(0);
while (!st1.empty() || !st2.empty() || carry > 0) {
int adder1 = 0;
int adder2 = 0;
if (!st1.empty()) {
adder1 = st1.top();
st1.pop();
}
if (!st2.empty()) {
adder2 = st2.top();
st2.pop();
}
int sum = adder1 + adder2 + carry;
carry = sum >= 10 ? 1 : 0;
sum = sum >= 10 ? sum - 10 : sum;
ListNode* cur = new ListNode(sum);
cur->next = dummy->next;
dummy->next = cur;
}
return dummy->next;
}
};
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46
Python 代码如下：
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution(object):
def addTwoNumbers(self, l1, l2):
st1 = []
st2 = []
while l1:
st1.append(l1.val)
l1 = l1.next
while l2:
st2.append(l2.val)
l2 = l2.next
carry = 0
dummy = ListNode(0)
while st1 or st2 or carry:
adder1 = st1.pop() if st1 else 0
adder2 = st2.pop() if st2 else 0
sum = adder1 + adder2 + carry
carry = 1 if sum >= 10 else 0
sum = sum - 10 if sum >= 10 else sum
cur = ListNode(sum)
cur.next = dummy.next
dummy.next = cur
return dummy.next
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27
复杂度分析：
- 时间复杂度：O(max(M,N))，M 和 N 分别是链表 a 和 b 的长度；
- 空间复杂度：O(1)，只使用了常数的空间。
总结
「求加法」系列题目都不难，其实就是「列竖式」计算；
需要注意的是：
1、 while循环结束条件；
2、 遍历两个「加数」不要越界；
3、 进位；
4、 链表在插入的时候如何进行反转；
DDKK.COM 弟弟快看-教程，程序员编程资料站，版权归原作者所有
本文经作者：负雪明烛 授权发布，任何组织或个人未经作者授权不得转发