问题描述:
You are given two linked lists representing two non-negative numbers. 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.
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
原问题链接:https://leetcode.com/problems/add-two-numbers/
问题分析
这个问题是一个对加法计算过程的模拟,相对来说比较简单。主要有这么几个要点:
1. 两个列表都有元素的时候,它们计算的和是(l1.val + l2.val + carry) % 10,carry = (l1.val + l2.val + carry) / 10
2. 当一个列表没有元素的时候,它们计算的和是(l1.val + carry) % 10, carry = (l1.val + carry) / 10,根据哪个列表有元素设置哪个。
3. 当两个列表都遍历完之后还要根据进位来判断是否需要新建一个节点。
4. 因为要返回结果链表,所以需要建立一个临时的节点,并保存它。以后每次计算出一个节点就将它加入到临时节点的后面。最后返回临时节点的后面那个几点作为最终结果。
根据这个思路,我们可以得到如下的一种实现:
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ public class Solution { public ListNode addTwoNumbers(ListNode l1, ListNode l2) { ListNode temp = new ListNode(0); int sum = 0, carry = 0; ListNode cur = temp; while(l1 != null && l2 != null) { sum = (l1.val + l2.val + carry) % 10; carry = (l1.val + l2.val + carry) / 10; ListNode node = new ListNode(sum); cur.next = node; cur = node; l1 = l1.next; l2 = l2.next; } while(l1 != null) { sum = (l1.val + carry) % 10; carry = (l1.val + carry) / 10; ListNode node = new ListNode(sum); cur.next = node; cur = node; l1 = l1.next; } while(l2 != null) { sum = (l2.val + carry) % 10; carry = (l2.val + carry) / 10; ListNode node = new ListNode(sum); cur.next = node; cur = node; l2 = l2.next; } if(carry != 0) { ListNode node = new ListNode(carry); cur.next = node; } return temp.next; } }
这种方式相对来说比较简单直观,但是显得有点冗长。根据问题本身,这里还是有一些可以优化的地方。比如说我们可以不需要在开头定义sum变量,我们可以通过carry变量来计算。另外,根据两个链表判断是否为空的逻辑可以稍微调整一下。我们可以将它修改成两个判断,如果l1 != null, carry += l1.val。如果l2 != null, carry += l2.val。这样在每个判断合格的条件里将l1, l2往后移。这样可以得到一个代码更加简洁的版本:
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ public class Solution { public ListNode addTwoNumbers(ListNode l1, ListNode l2) { ListNode temp = new ListNode(0); int carry = 0; ListNode cur = temp; while(l1 != null || l2 != null) { if(l1 != null) { carry += l1.val; l1 = l1.next; } if(l2 != null) { carry += l2.val; l2 = l2.next; } cur.next = new ListNode(carry % 10); cur = cur.next; carry /= 10; } if(carry != 0) { cur.next = new ListNode(carry); } return temp.next; } }
相关推荐
You are given two non-empty linked lists ... 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. java AC版本
leetcode:Add Two Numbers(java)
自己写的一个完整的程序,包括main函数,在VS上面提交通过,但是放到leetcode上面会出现问题;只是作为一个参考,一起学习学习0.o!解决的问题有:第一:两个链表的最后一个值相加后进位的问题;第二:两个链表的...
leetcode leetcode练习 twosum 问题 ;add two numbers问题;reverse integer问题;最大不重复子字符串长度问题;atoi问题;
leetcode 分类leetcode 问题分类 leetcode代码仓库,我的解题...#2:Add Two Numbers 分而治之 #53:Maximum Subarray 队列/集 #3:Longest Substring Without Repeating Characters 优先队列 #23:Merge k Sorted Lists
leetcode 知乎 此项目介绍 此项目旨在是为leetcode里面的习题...Numbers: Longest Substring Without Repeat... Median of Two Sorted Arrays Longest Palindromic Substring ZigZag Conversion Reverse Integer Strin
Add Two Numbers], Linked list 2017.06.13 打卡[LeetCode 200. Number of Islands], BFS 2017.06.14 打卡[LeetCode 3. Longest Substring Without Repeating Characters], N/A 2017.06.15 打卡[LeetCode 407. ...
Add Two Numbers 3. Longest Substring Without Repeating Characters 4. Median of Two Sorted Arrays 5. Longest Palindromic Substring 7. Reverse Integer 9. Palindrome Number 11. Container With Most Water ...
第二题:Add Two Numbers 第三题:Longest Substring Without Repeating Characters 这题是让你从一个字符串中找到最大不重复的字串的长度。 第一钟解题思路就是两个for循环来遍历出每一种字串,然后将这个字串放在...
#leetcode 001_Medium: Two Sum.利用哈希表(在O(1)时间复杂度内查找某个元素)。遍历数组,查找map里是否containsKey(target-nums[i]),如果则返回,否则将nums[i]放入map中(map.put(nums[i],i)。 002_Medium: Add ...
python python_leetcode面试题解之两数相加AddTwoNumbers
Add Two Numbers struct复习 可以在定义结构体的同时定义结构体变量: struct stu{ char *name; //姓名 int num; //学号 int age; //年龄 char group; //所在学习小组 float score; //成绩 } stu1, stu2; 如果只需要...
Numbers JavaScript O(n) O(1) Medium 4 Median of Two Sorted Arrays JavaScript O(log (m+n)) O(1) Hard 7 Reverse Integer JavaScript O(n) O(1) Easy 9 Palindrome Number JavaScript O(n) O(1) Easy 19 Remove ...
leetcode 答案leetcode javascript 中 leetcode 测试的答案 twoSum addTwoNumbers
蓄水池算法 leetcode Leetcode Solutions Continue updating... lt: leetcode jz: 剑指Offer ...Two ...Add ...Numbers easy linked list lt.4 Median of Two Sorted Arrays hard [python] lt.5 Longest Pa
numbers C++: 击败 69.99% python : 击败93.67% ###2016年1月23日 ####题号3: Longest Substring Without Repeating Characters C++: 击败 64.54% python : 击败86.59% ###2016年1月23日 ####题号4: Median of...
leetcode 2 和 c #Chao Xu 的 LeetCode 笔记 # 标题 困难 分析 代码 1 二和 中等的 [C++] (./C++/Two Sum.cpp), [Java] (./Java/Two Sum.java) 2 两个数相加 中等的 [C++] (./C++/Add Two Numbers.cpp), [Java] (./...
leetcode 答案 leet code 这是我的leetcode答案,语言...Add Two Numbers Longest Substring Without Repeating Characters Median of Two Sorted Arrays Longest Palindromic Substring Regular Expression Matching
两数相加(Add Two Numbers) 2018.9.25 翻转二叉树(Invert Binary Tree) 2018.9.25 环形链表(Linked List Cycle) 2018.9.25 环形链表 II(Linked List Cycle II) 2018.9.26 删除排序链表中的重复元素 II...