上一篇文章我们给出了今天的题目,大家有尝试过吗?
题目:两数相加
描述:描述:给出两个 非空 的链表用来表示两个非负的整数。其中,它们各自的位数是按照 逆序 的方式存储的,并且它们的每个节点只能存储 一位 数字。如果我们将这两个数相加起来,则会返回一个新的链表来表示它们的和。您可以假设除了数字 0 之外,这两个数都不会以 0 开头。
示例:
输入:(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出:7 -> 0 -> 8
原因:342 + 465 = 807
解析
这个题目相对基础很多,就是两个单链表的处理,我们只要注意进位即可。不过我们要处理好几种特殊情况:
当两个链表为 (4 -> 5) 和 (4 -> 5) 时,因为进位原因,所以结果为 (8 -> 0 -> 1)
当两个链表为 (4 -> 4) 和 (4 -> 5 -> 1) 时,因为两个链表长度不同,所以结果为 (8 -> 9 -> 1)
只要注意处理好以上问题,其它都是常规操作,一起看下参考代码吧:
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
// 用来标记返回结果的头结点,增加一个结点可以使代码简单
ListNode result = new ListNode(-1);
// 记录当前位置的值
int cur = ;
// 进位标志
int identify = ;
// 用另一个结点来构建链表,这样就不会丢失头结点指针了
ListNode resultHandle = result;
// 避免长度不一致
while (l1!=null || l2!=null){
int a = l1!=null?l1.val:;
int b = l2!=null?l2.val:;
// 计算当前值
cur = a + b + identify;
// 更新进位标志
identify = cur/10;
// 更新当前值
cur %%= 10;
// 当前值存入链表
resultHandle.next = new ListNode(cur);
if(l1!=null){
l1 = l1.next;
}
if(l2!=null){
l2 = l2.next;
}
resultHandle = resultHandle.next;
}
// 注意进位
if(identify!=){
resultHandle.next = new ListNode(identify);
}
// 去除头结点
return result.next;
}
总结
好了,本次题目就是这么简单,主要在于细致,处理好各种边界问题就好。以后我会对题目进行适当的筛选,尽量分享一些能够给我们启发的题目。不过全部的题目都会上传到我的github。
相关源码已经发布在我的github项目:https://github.com/LtLei/articles中,您可以到 /leetcode/code/ 目录下查看。
下题预告
题目:无重复字符的长子串
描述:给定一个字符串,请你找出其中不含有重复字符的长子串的长度。
示例:
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的长子串是 "abc",所以其长度为 3。
更多文章正在火速连载中,感谢您的关注!