[LeetCode] 445. Add Two Numbers II 两个数字相加之二
LeetCode 数字 两个 II add 之二 two 相加
2023-09-27 14:28:37 时间
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】让字符串成为回文串的最少插入次数 [H](动态规划)
- 【LeetCode】阶乘后的零 [M](数学)
- sql:Leetcode--计算特殊奖金
- LeetCode_动态规划_数位 dp_困难_1012.至少有 1 位重复的数字
- LeetCode_位运算_中等_318.最大单词长度乘积
- LeetCode_贪心算法_双端队列_中等_402.移掉 K 位数字
- LeetCode_排列组合_中等_357.统计各位数字都不同的数字个数
- LeetCode_优先级队列_中等_373.查找和最小的 K 对数字
- LeetCode_位运算_简单_405.数字转换为十六进制数
- LeetCode_位运算_中等_260.只出现一次的数字 III
- LeetCode_动态规划_中等_198.打家劫舍
- LeetCode_阶乘_中等_172.阶乘后的零
- LeetCode_字符串_简单_67.二进制求和
- LeetCode·每日一题·1124.表现良好的最长时间段·前缀和
- LeetCode·每日一题·788.旋转数字·模拟
- LeetCode·233.数字1的个数·数学
- LeetCode-136. 只出现一次的数字(java)
- LeetCode-剑指 Offer 22. 链表中倒数第k个节点(Goland实现)
- LeetCode-剑指 Offer 03. 数组中重复的数字(Goland实现)
- [LeetCode] 507. Perfect Number 完美数字
- [LeetCode] 911. Online Election 在线选举
- leetcode 1356 根据数字二进制下1的数目排序