[LeetCode] 2. Add Two Numbers 两个数字相加
You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order 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.
Example:
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4) Output: 7 -> 0 -> 8 Explanation: 342 + 465 = 807.
这道并不是什么难题,算法很简单,链表的数据类型也不难,就是建立一个新链表,然后把输入的两个链表从头往后撸,每两个相加,添加一个新节点到新链表后面。为了避免两个输入链表同时为空,我们建立一个 dummy 结点,将两个结点相加生成的新结点按顺序加到 dummy 结点之后,由于 dummy 结点本身不能变,所以用一个指针 cur 来指向新链表的最后一个结点。好,可以开始让两个链表相加了,这道题好就好在最低位在链表的开头,所以可以在遍历链表的同时按从低到高的顺序直接相加。while 循环的条件两个链表中只要有一个不为空行,由于链表可能为空,所以在取当前结点值的时候,先判断一下,若为空则取0,否则取结点值。然后把两个结点值相加,同时还要加上进位 carry。然后更新 carry,直接 sum/10 即可,然后以 sum%10 为值建立一个新结点,连到 cur 后面,然后 cur 移动到下一个结点。之后再更新两个结点,若存在,则指向下一个位置。while 循环退出之后,最高位的进位问题要最后特殊处理一下,若 carry 为1,则再建一个值为1的结点,代码如下:
C++ 解法:
class Solution { public: ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) { ListNode *dummy = new ListNode(-1), *cur = dummy; int carry = 0; while (l1 || l2) { int val1 = l1 ? l1->val : 0; int val2 = l2 ? l2->val : 0; int sum = val1 + val2 + carry; carry = sum / 10; cur->next = new ListNode(sum % 10); cur = cur->next; if (l1) l1 = l1->next; if (l2) l2 = l2->next; } if (carry) cur->next = new ListNode(1); return dummy->next; } };
Java 解法:
public class Solution { public ListNode addTwoNumbers(ListNode l1, ListNode l2) { ListNode dummy = new ListNode(-1); ListNode cur = dummy; int carry = 0; while (l1 != null || l2 != null) { int d1 = l1 == null ? 0 : l1.val; int d2 = l2 == null ? 0 : l2.val; int sum = d1 + d2 + carry; carry = sum >= 10 ? 1 : 0; cur.next = new ListNode(sum % 10); cur = cur.next; if (l1 != null) l1 = l1.next; if (l2 != null) l2 = l2.next; } if (carry == 1) cur.next = new ListNode(1); return dummy.next; } }
在 CareerCup 上的这道题还有个 Follow Up,把链表存的数字方向变了,原来是表头存最低位,现在是表头存最高位,请参见我的另一篇博客 2.5 Add Two Numbers 两个数字相加 。
Github 同步地址:
https://github.com/grandyang/leetcode/issues/2
类似题目:
参考资料:
https://leetcode.com/problems/add-two-numbers/
相关文章
- leetcode 201. 数字范围按位与 解题报告
- LeetCode高频题:int数字x被拆为p1,p2,p3,输入N必须满足N=p1+p2/p3,p2/p3整除,N有多少种分数形式
- JS leetcode 找到所有数组中消失的数字 题解分析
- [LeetCode] Merge Intervals
- [LeetCode]392. 判断子序列
- [LeetCode]剑指 Offer 57. 和为s的两个数字
- [LeetCode]1295. 统计位数为偶数的数字
- 201、【数组】leetcode ——面试题 17.05. 字母与数字(C++版本)
- 152、【动态规划】leetcode ——416. 分割等和子集:滚动数组+二维数组(C++版本)
- leetcode第72场双周赛记录
- 【LeetCode】112. Path Sum
- LeetCode 258 Add Digits(数字相加,数字根)
- LeetCode——Longest Consecutive Sequence
- 查找至少连续出现三次的所有数字/连续3天的日期【LeetCode】
- [LeetCode] 1304. Find N Unique Integers Sum up to Zero 和为零的N个唯一整数
- [LeetCode] 1012. Numbers With Repeated Digits 至少有1位重复的数字
- [LeetCode] 970. Powerful Integers 强力数字
- [LeetCode] 961. N-Repeated Element in Size 2N Array 在大小为2N的数组中重复N次的数字
- [LeetCode] 949. Largest Time for Given Digits 由给定数字组成的最大时间
- [LeetCode] 861. Score After Flipping Matrix 翻转矩阵后的分数
- [LeetCode] 685. Redundant Connection II 冗余的连接之二
- [LeetCode] Largest Number At Least Twice of Others 至少是其他数字两倍的最大数
- [LeetCode] Self Dividing Numbers 自整除数字
- [LeetCode] Perfect Number 完美数字
- [LeetCode] 438. Find All Anagrams in a String 找出字符串中所有的变位词
- [LeetCode] Reconstruct Original Digits from English 从英文中重建数字
- [LeetCode] Remove Duplicate Letters 移除重复字母
- [LeetCode] Symmetric Tree 判断对称树
- Leetcode——2. Add Two Numbers
- leetcode 208. Implement Trie (Prefix Tree) 实现 Trie (前缀树) (中等)