1.题目描述
给定两个非空链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储单个数字。将这两数相加会返回一个新的链表。
你可以假设除了数字 0 之外，这两个数字都不会以零开头。
进阶:
如果输入链表不能修改该如何处理？换句话说，你不能对列表中的节点进行翻转。
示例:
输入: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
输出: 7 -> 8 -> 0 -> 7
2.解法一：反转链表
2.1 思路
（1）将两个链表反转，就变成了Leetcode上的第二道题目“2.两数相加”；
（2）然后就是一样的思路：题中链表顺序正好是低位到高位，先低位相加，有进位保持，下一位计算加上进位，直到最高位相加，如果有进位，生成新的结点保存。
2.2 代码
class Solution {
public:
//反转链表
ListNode* reverseList(ListNode* l3) {
if (!l3) return NULL;
ListNode* r = new ListNode(l3->val);
ListNode* h = r;
ListNode* cur = l3->next;
while (cur) {
ListNode* temp = new ListNode(cur->val);
temp->next = h;
h = temp;
cur = cur->next;
}
return h;
}
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
//逆序
l1 = Solution::reverseList(l1);
l2 = Solution::reverseList(l2);
unsigned int carry = ; //进位
ListNode* Hl3 = new ListNode();
ListNode* l3 = Hl3;
int a = ;
int b = ;
int temp = ;
while (l1 != NULL || l2 != NULL)
{
//判断a和b的取值
if (l1 == NULL) a = ;
else a = l1->val;
if (l2 == NULL) b = ;
else b = l2->val;
temp = (a + b + carry) % ;
//有无进位
if ((a + b + carry) / != )
carry = ;
else
carry = ;
//创建新结点，保存temp
l3->next = new ListNode(temp);
l3 = l3->next;
if (l1) l1 = l1->next;
if (l2) l2 = l2->next;
}
//最后的进位
if (carry == ) {
l3->next = new ListNode();
}
//还原链表
Hl3->next = Solution::reverseList(Hl3->next);
return Hl3->next;
}
};
3.解法二：不允许反转（进阶）
3.1 思路
关键还是在于逆序，栈结构适应于这种情况。不需要考虑空间复杂性的话，为了方便，使用三个栈
- 前两个栈s1和s2逆序保存两个链表l1和l2的结点值；
- 第三个栈s3来保存前两个栈相加的结果，还原链表顺序；
3.2 代码
#include <iostream>
#include <stack> using namespace std; struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
}; class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
stack<int> s1;
stack<int> s2;
stack<int> s3; ListNode* Hl3 = new ListNode();
ListNode* l3 = Hl3; //遍历两个链表入栈，进行逆序
while (l1 != NULL) {
s1.push(l1->val);
l1 = l1->next;
}
while (l2 != NULL) {
s2.push(l2->val);
l2 = l2->next;
} //用栈来相加
int a = ;
int b = ;
int temp = ;
int carry = ; while (!s1.empty() || !s2.empty()) {
a = s1.size() == ? : s1.top();
b = s2.size() == ? : s2.top();
temp = a + b + carry; //有无进位
carry = temp / == ? : ; s3.push(temp % ); /*---常见错误总结---*/
//不空，才能出栈
if(!s1.empty()) s1.pop();
if(!s2.empty()) s2.pop();
}
if (carry == )
s3.push(); //恢复顺序
while (!s3.empty()) {
l3->next = new ListNode(s3.top());
l3 = l3->next;
s3.pop();
}
return Hl3->next;
}
}; int main()
{
ListNode* p1 = new ListNode();
ListNode* p2 = new ListNode();
ListNode* p3 = new ListNode();
ListNode* p4 = new ListNode();
p1->next = p2;
p2->next = p3;
p3->next = p4;
p4->next = NULL; ListNode* q1 = new ListNode();
ListNode* q2 = new ListNode();
ListNode* q3 = new ListNode();
q1->next = q2;
q2->next = q3;
q3->next = NULL; Solution test;
ListNode* t1 = test.addTwoNumbers(p1, q1);
while (t1) {
cout << t1->val << endl;
t1 = t1->next;
}
return ;
}