You are given two linked lists representing two non-negative numbers. 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.
You may 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
2. Add Two Numbers 的变形,之前的题最高位在链表末位,此题链表头部表示高位,尾部表示低位,不允许反转链表。两个数相加需要从低位开始。可以利用Stack的特点后进先出,遍历两个链表,将数字分别压入两个栈s1和s2,然后开始循环,如果栈不为空,则将栈顶数字加入sum中。
Java:
public class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
Stack<Integer> s1 = new Stack<Integer>();
Stack<Integer> s2 = new Stack<Integer>(); while(l1 != null) {
s1.push(l1.val);
l1 = l1.next;
};
while(l2 != null) {
s2.push(l2.val);
l2 = l2.next;
} int sum = 0;
ListNode list = new ListNode(0);
while (!s1.empty() || !s2.empty()) {
if (!s1.empty()) sum += s1.pop();
if (!s2.empty()) sum += s2.pop();
list.val = sum % 10;
ListNode head = new ListNode(sum / 10);
head.next = list;
list = head;
sum /= 10;
} return list.val == 0 ? list.next : list;
}
}
Python:
class Solution(object):
def addTwoNumbers(self, l1, l2):
stk1, stk2 = [], []
while l1:
stk1.append(l1.val)
l1 = l1.next
while l2:
stk2.append(l2.val)
l2 = l2.next prev, head = None, None
sum = 0
while stk1 or stk2:
sum /= 10
if stk1:
sum += stk1.pop()
if stk2:
sum += stk2.pop() head = ListNode(sum % 10)
head.next = prev
prev = head if sum >= 10:
head = ListNode(sum / 10)
head.next = prev return head
C++:
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
stack<int> stk1, stk2;
while (l1) {
stk1.emplace(l1->val);
l1 = l1->next;
}
while (l2) {
stk2.emplace(l2->val);
l2 = l2->next;
} ListNode *prev = nullptr, *head = nullptr;
int sum = 0;
while (!stk1.empty() || !stk2.empty()) {
sum /= 10;
if (!stk1.empty()) {
sum += stk1.top();
stk1.pop();
} if (!stk2.empty()) {
sum += stk2.top();
stk2.pop();
} head = new ListNode(sum % 10);
head->next = prev;
prev = head;
} if (sum >= 10) {
head = new ListNode(sum / 10);
head->next = prev;
} return head;
}
};
相似题目:
[LeetCode] 2. Add Two Numbers 两个数字相加
[LeetCode] 67. Add Binary 二进制数相加
[LeetCode] 445. Add Two Numbers II 两个数字相加之二
[LeetCode] 445. Add Two Numbers II 两个数字相加之二的更多相关文章
-
[LeetCode] Add Two Numbers II 两个数字相加之二
You are given two linked lists representing two non-negative numbers. The most significant digit com ...
-
LeetCode 445. Add Two Numbers II (两数相加 II)
题目标签:Linked List 题目给了我们两个 数字的linked list,让我们把它们相加,返回一个新的linked list. 因为题目要求不能 reverse,可以把 两个list 的数字 ...
-
[leetcode]445. Add Two Numbers II 两数相加II
You are given two non-empty linked lists representing two non-negative integers. The most significan ...
-
LeetCode 445 Add Two Numbers II
445-Add Two Numbers II You are given two linked lists representing two non-negative numbers. The mos ...
-
445 Add Two Numbers II 两数相加 II
给定两个非空链表来代表两个非负整数.数字最高位位于链表开始位置.它们的每个节点只存储单个数字.将这两数相加会返回一个新的链表.你可以假设除了数字 0 之外,这两个数字都不会以零开头.进阶:如果输入链表 ...
-
LeetCode 445. Add Two Numbers II(链表求和)
题意:两个非空链表求和,这两个链表所表示的数字没有前导零,要求不能修改原链表,如反转链表. 分析:用stack分别存两个链表的数字,然后从低位开始边求和边重新构造链表. Input: (7 -> ...
-
【LeetCode】445. Add Two Numbers II 解题报告(Python & C++)
作者: 负雪明烛 id: fuxuemingzhu 个人博客: http://fuxuemingzhu.cn/ 目录 题目描述 题目大意 解题方法 先求和再构成列表 使用栈保存节点数字 类似题目 日期 ...
-
【Leetcode】445. Add Two Numbers II
You are given two non-empty linked lists representing two non-negative integers. The most significan ...
-
445. Add Two Numbers II【Medium】【两个链表求和】
You are given two non-empty linked lists representing two non-negative integers. The most significan ...
随机推荐
-
sql server 取随机行
--从table_name中随机取n行 select top n * from table_name order by NEWID()
-
神器——Chrome开发者工具(一)
这里我假设你用的是Chrome浏览器,如果恰好你做web开发,或者是比较好奇网页中的一些渲染效果并且喜欢折腾,那么你一定知道Chrome的开发者工具了.其实其他浏览器也有类似工具,比如Firefox下 ...
-
iOS人脸识别核心代码(备用)
for (int i = 0; i < 1; i++) { //< [arr count]; i++) { CIFaceFeature *feature = [arr objectAtIn ...
-
algorithms中计算时间的渐近表示
1.大写Ο符号大写Ο符号给出了函数f的一个上限. 定义[大写Ο符号]:f(n)=Ο(g(n)),当且仅当存在正的常数c和n0,使得对于所有的n≥n0,有 f(n)≤c*g(n) 上述定义表明,函数f至 ...
-
Sql数据保存到Excel文件中
public string ExportExcel( DataSet ds,string saveFileName) { try { if (ds == null) return "数据库为 ...
-
Selenium也是一个用于Web应用程序测试的工具
Selenium也是一个用于Web应用程序测试的工具.Selenium测试直接运行在浏览器中,就像真正的用户在操作一样.支持的浏览器包括IE.Mozilla Firefox.Mozilla Suite ...
-
What does a Bayes factor feel like?(转)
A Bayes factor (BF) is a statistical index that quantifies the evidence for a hypothesis, compared t ...
-
jQuery模块化开发
//定义了命名空间. var Itcast = {}; //定义第二级别的 命名空间. var Itcast.Model = {}; var Itcast.Model.UIJs = (function ...
-
SP283 NAPTIME - Naptime
SP283 NAPTIME - Naptime 题意: 在某个星球上,一天由N小时构成.我们称0-1点为第一个小时,1-2点为第二个小时,以此类推.在第i个小时睡觉能恢复Ui点体力.在这座星球上住着一 ...
-
SQL、索引
(二)数据库索引 数据库索引是用于提高数据库表的数据访问速度的. 数据库索引的特点: a)避免进行数据库全表的扫描,大多数情况,只需要扫描较少的索引页和数据页,而不是查询所有数据页.而且对于非聚集索引 ...