【LeetCode学习记录01】两数相加(Java实现)
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了【LeetCode学习记录01】两数相加(Java实现),小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含4634字,纯文字阅读大概需要7分钟。
内容图文
![【LeetCode学习记录01】两数相加(Java实现)](/upload/InfoBanner/zyjiaocheng/639/2fb795ca2db24f2e8d57726e6b12c321.jpg)
2. 两数相加(Java实现)
题目:给出两个 非空 的链表用来表示两个非负的整数。其中,它们各自的位数是按照 逆序 的方式存储的,并且它们的每个节点只能存储 一位 数字。
如果,我们将这两个数相加起来,则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外,这两个数都不会以 0 开头。
示例:
输入:(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出:7 -> 0 -> 8
原因:342 + 465 = 807
看了大佬们的思路后重新整理的代码
思路:
- 将两个链表看成是相同长度的进行遍历,如果一个链表较短则在前面补0,eg: 987 + 23 = 987 + 023 = 1010
- 每一位计算的同时需要考虑上一位的进位问题,而当前位计算结束后同样需要更新进位值
- 如果两个链表全部遍历完毕后,进位值为 1,则在新链表最前方添加节点 1。这里解释一下,因为最终你的结果是按链表一位一位返回的,所以不管中间你有多少进位,这些进位你都在计算时加进去了,直到最后一位如果有进位的话,就要新插入一个结点(val=1)。
- 最后构造返回结果的链表。说白了就是在Java中的链表操作,这一步一定要深刻理解一个问题:Java中的对象与对象的引用。如果觉得不太清楚,请看浅谈Java中的对象和引用。简单来说,我们先创建一个头对象,两个引用head,temp都指向这个头。接下来,head不动,temp作为工具人去链接新对象(结点)(temp.next=newNode;),然后指向链表尾部的结点*(temp = temp.next;)*。head一直指向链表头,用来返回结果。(注:因为头结点不是结果的一部分,所以返回的是head.next)
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
//创建一个头结点对象
ListNode head = new ListNode(0);
//两个引用head和temp都指向这个对象,head用来指向链表头,temp是工具人(有点像C语言中移动的指针)
ListNode temp = head;
//进位标志carry
int carry = 0;
//每一位的求和sum
int sum =0;
while(l1!=null||l2!=null){
int x = null==l1?0:l1.val;
int y = null==l2?0:l2.val;
sum = x+y+carry;
//计算本位是否有进位
carry = sum/10;
//插入本位的计算结果
ListNode newNode = new ListNode(sum%10);
//将新结点插入到链表中
temp.next=newNode;
//指针移动,temp一直指向链表的尾部
temp = temp.next;
if(l1 != null)
l1 = l1.next;
if(l2 != null)
l2 = l2.next;
}
//最高位如果有进位,则插入一个新结点(val=1)
if(carry>0){
temp.next = new ListNode(carry);
}
//head指向的头结点不是结果的一部分,真正的返回结果从head.next开始
return head.next;
}
}
- 结果:
- 相信很多人和我一样看着head.next觉得很不爽,为什么要搞一个没用的头结点,我希望我的链表就是结果,而不是再去掉一个头结点。于是我将上面的代码稍微修改了一点,解决了上面的问题,其实很简单,加个判断就行了。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode head = null;
ListNode temp = null;
//进位标志carry
int carry = 0;
//每一位的求和sum
int sum =0;
while(l1!=null||l2!=null){
int x = null==l1?0:l1.val;
int y = null==l2?0:l2.val;
sum = x+y+carry;
//计算本位是否有进位
carry = sum/10;
//插入本位的计算结果
ListNode newNode = new ListNode(sum%10);
//将新结点插入到链表中
//如果头结点为null,就将head指向新创建的结点
if(head==null){
head = newNode;
temp = head;
}else{
temp.next=newNode;
temp = temp.next;
}
if(l1 != null)
l1 = l1.next;
if(l2 != null)
l2 = l2.next;
}
//最高位如果有进位,则插入一个新结点(val=1)
if(carry>0){
temp.next = new ListNode(carry);
}
//head指向的头结点不是结果的一部分,真正的返回结果从head.next开始
return head.next;
}
}
- 结果:
记录下我自己的不成熟的想法
看到这个题目,我最先想到的就是,把给的输入的两个链表l1和l2转化为整型数,相加得到结果,再将结果转为链表返回。(如此愚笨的方法你可以看出我的算法水平了。。。平时不努力,编码徒伤悲。。。,所以要好好敲代码啊!)
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
StringBuilder str1 = new StringBuilder();
StringBuilder str2 = new StringBuilder();
//遍历l1链表,存储到str1中
while(l1!=null){
str1.append(l1.val);
l1=l1.next;
}
//遍历l2链表,存储到str2中
while(l2!=null){
str2.append(l2.val);
l2=l2.next;
}
try{
//将l1、l2中字符串逆序后准成int类型
int r1 = Integer.parseInt(str1.reverse().toString());
int r2 = Integer.parseInt(str2.reverse().toString());
//求和得到结果
int r = r1+r2;
// System.out.println(r1+" + "+r2+"="+" "+r);
//将结果r从低位到高位插入到结果链表中
ListNode head = null;
if(r==0){
return new ListNode(0);
}
while(r!=0){
ListNode newNode = new ListNode(r%10);
if(head ==null) {
head = newNode;
}else {
ListNode tmp = head;
while(tmp.next!=null) {
tmp = tmp.next;
}
tmp.next = newNode;
}
r = r/10;
}
return head;
}catch(Exception e){
}
return null;
}
}
- 结果:
?这里面的问题是:用int型来存储计算结果,但测试用例的值远大于int型所能表示的范围。我看了一些帖子,据说long也不行,用 BigDecimal 可以通过。
内容总结
以上是互联网集市为您收集整理的【LeetCode学习记录01】两数相加(Java实现)全部内容,希望文章能够帮你解决【LeetCode学习记录01】两数相加(Java实现)所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。