两数相加
题目
给你两个 非空 的链表,表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的,并且每个节点只能存储 一位 数字。
请你将两个数相加,并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外,这两个数都不会以 0 开头。
示例 1:
输入:l1 = [2,4,3], l2 = [5,6,4] 输出:[7,0,8] 解释:342 + 465 = 807.
示例 2:
输入:l1 = [0], l2 = [0] 输出:[0]
示例 3:
输入:l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9] 输出:[8,9,9,9,0,0,0,1]
提示:
- 每个链表中的节点数在范围
[1, 100]
内 0 <= Node.val <= 9
- 题目数据保证列表表示的数字不含前导零
解题方法一
/**
* 先获取两个链表的长度len1、len2,比较出较长longList和较短shortList链表并用指针记录curL、curS,
* 然后分三种情况:
* 1)当两条链表都有元素时 curS != null
* - 将两条链表对应节点元素值与进位值相加,得到的此值%10得出此位上的值并直接赋给curL.val
* - 将相加结果/10 求得进位值
* - last = curL; last作为记录最后一个节点,以便最后需要进位时直接再其后增加
* - curL、curS向后移动;
* 2)当较短链表没有元素时 curL != null
* - 将curL对应节点元素值与进位值相加,得到的此值%10得出此位上的值并直接赋给curL.val
* - 将相加结果/10 求得进位值
* - last = curL;
* - curL向后移动;
* 3)当两条链表都没元素时
* - 判断最后进位是否为0
* - carry != 0 表示需要进位 last.next = new ListNode(1);
* <p>
* 最后返回longList
*
* @param l1
* @param l2
* @return
*/
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
// 获取两个链表长度
int len1 = getLength(l1);
int len2 = getLength(l2);
// 创建较长链表和较短链表的指针
ListNode longList = len1 >= len2 ? l1 : l2;
ListNode shortList = longList == l1 ? l2 : l1;
ListNode curL = longList;
ListNode curS = shortList;
// last作为记录最后一个节点,以便最后需要进位时直接再其后增加
ListNode last = curL;
int carry = 0; //进位标志
int curNum = 0;
//当短链表不为空时,两条链表同时都有值
while (curS != null) {
curNum = curL.val + curS.val + carry;
curL.val = (curNum % 10);
carry = curNum / 10;
last = curL;
curL = curL.next;
curS = curS.next;
}
// 当跳出上一个循环时,表明短链表为空
while (curL != null) {
curNum = curL.val + carry;
curL.val = (curNum % 10);
carry = curNum / 10;
last = curL;
curL = curL.next;
}
// 当跳出上一个循环时,表明两条链表全部节点遍历结束
// 如果有进位 则在最后新增节点1
if (carry != 0) {
last.next = new ListNode(1);
}
return longList;
}
// 求链表长度
private static int getLength(ListNode head) {
int length = 0;
while (head != null) {
length++;
head = head.next;
}
return length;
}
解题方法二
/**
* 总体分为两步: 按位相加 and 进位
* 这个方法代码比较容易理解
* 需要注意特殊情况的处理:
* 当l2.len > l1.len
* 当最后需要进位时
*
* @param l1
* @param l2
* @return
*/
public ListNode addTwoNumbers2(ListNode l1, ListNode l2){
ListNode head1 = l1;
ListNode head2 = l2;
// 按位相加
while (head1 != null){
if (head2 != null){
head1.val += head2.val;
head2 = head2.next;
}
if (head1.next == null && head2 != null){
head1.next = head2;
break;
}
head1 = head1.next;
}
// 进位
merge(l1);
return l1;
}
// 进位
public void merge(ListNode head1) {
while (head1 != null){
if (head1.val >= 10){
head1.val = head1.val % 10;
if (head1.next == null){
head1.next = new ListNode(0);
}
head1.next.val += 1;
}
head1 = head1.next;
}
}
微信关注
本站为非盈利性站点,所有资源、文章等仅供学习参考,并不贩卖软件且不存在任何商业目的及用途,如果您访问和下载某文件,表示您同意只将此文件用于参考、学习而非其他用途。
本站所发布的一切软件资源、文章内容、页面内容可能整理来自于互联网,在此郑重声明本站仅限用于学习和研究目的;并告知用户不得将上述内容用于商业或者非法用途,否则一切后果请用户自负。
如果本站相关内容有侵犯到您的合法权益,请仔细阅读本站公布的投诉指引页相关内容联系我,依法依规进行处理!
作者:理想
链接:https://www.imyjs.cn/archives/559
本站所发布的一切软件资源、文章内容、页面内容可能整理来自于互联网,在此郑重声明本站仅限用于学习和研究目的;并告知用户不得将上述内容用于商业或者非法用途,否则一切后果请用户自负。
如果本站相关内容有侵犯到您的合法权益,请仔细阅读本站公布的投诉指引页相关内容联系我,依法依规进行处理!
作者:理想
链接:https://www.imyjs.cn/archives/559
THE END
0
二维码


两数相加
题目
给你两个 非空 的链表,表示两个非负的整数。……

文章目录
关闭

共有 0 条评论