https://leetcode-cn.com/problems/add-two-numbers-ii/description/
给定两个非空链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储单个数字。将这两数相加会返回一个新的链表。
你可以假设除了数字 0 之外，这两个数字都不会以零开头。
进阶:
如果输入链表不能修改该如何处理？换句话说，你不能对列表中的节点进行翻转。
示例:
输入: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
输出: 7 -> 8 -> 0 -> 7
/**
* 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) {
stack s1;
stack s2;
while (l1) {
s1.push(l1->val);
l1 = l1->next;
}while (l2)
{
s2.push(l2->val);
l2 = l2->next;
}
stack q;
int gap = 0;
int sum = 0;
while (!s1.empty() && !s2.empty()) {
sum = s1.top() + s2.top() + gap;
s1.pop();
s2.pop();
if (sum >= 10) {
sum %= 10;
gap = 1;
}
else {
gap = 0;
}
q.push(sum);
}
while (!s1.empty()) {
sum = gap + s1.top();
if (sum >= 10) {
sum %= 10;
gap = 1;
}
else {
gap = 0;
}
q.push(sum);
s1.pop();
}while (!s2.empty()) {
sum = gap + s2.top();
if (sum >= 10) {
sum %= 10;
gap = 1;
}
else {
gap = 0;
}
q.push(sum);
s2.pop();
}
if (gap) {
q.push(gap);
}
ListNode* Head = new ListNode(-1);
ListNode* cur = Head;
while (!q.empty()) {
cur->next = new ListNode(q.top());
cur = cur->next;
q.pop();
}
return Head->next;
}
};
【LeetCode|445. 两数相加 II】
文章图片
推荐阅读
- 数据结构与算法|【算法】力扣第 266场周赛
- leetcode|今天开始记录自己的力扣之路
- 数据结构|C++技巧（用class类实现链表）
- 数据结构学习指导|数据结构初阶（线性表）
- Python|Python 每日一练 二分查找 搜索旋转排序数组 详解
- 【LeetCode】28.实现strstr（） （KMP超详细讲解，sunday解法等五种方法，java实现）
- LeetCode-35-搜索插入位置-C语言
- leetcode python28.实现strStr()35. 搜索插入位置
- Leetcode Permutation I & II
- python|leetcode Longest Substring with At Most Two Distinct Characters 滑动窗口法