题目:
给定两个用链表表示的整数,每个节点包含一个数位。这些数位是反向存放的,也就是个位排在链表首部。编写函数对这两个整数求和,并用链表形式返回结果。
示例:
输入:(7 -> 1 -> 6) + (5 -> 9 -> 2),即617 + 295
输出:2 -> 1 -> 9,即912
进阶:思考一下,假设这些数位是正向存放的,又该如何解决呢?
示例:
输入:(6 -> 1 -> 7) + (2 -> 9 -> 5),即617 + 295
输出:9 -> 1 -> 2,即912
解题思路:
1.输入为2个链表,长度是不确定的,所以这里利用while循环来判断,退出循环的条件就是两个链表都为空时退出。
2.累加2个链表的val值,这里需要注意的是如果有进位,需要把进位累加到下一级的计算中。进位默认为0。去累加值取余为新的这一级的val的值。
3.当某一个链表下的指向为空时,则该值设置为零。
4.递归这两个链表,执行完一次累加以后,当前链表等于下一级的链表。每次给新的node赋值以后,移动指针到下一级node中。
5.最后返回这个新的链表。
代码:
public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
//定义一个头结点。
ListNode newNode = new ListNode(0);
//用来累计向下添加节点。
ListNode curr = newNode;
//进位符。
int carry = 0;
while (l1 != null || l2 != null) {
//判断如果某个节点为空,则该位的值为0
int val1 = l1 == null ? 0 : l1.val;
int val2 = l2 == null ? 0 : l2.val;
//累加
int sum = val1 + val2 + carry;
//进位
carry = sum / 10;
//取余
curr.next = new ListNode(sum % 10);
//继续向下
curr = curr.next;
l1 = l1 == null ? null : l1.next;
l2 = l2 == null ? null : l2.next;
}
//判断最后一次如果有进位,则添加新的节点。
if (carry != 0) {
curr.next = new ListNode(carry);
}
return newNode.next;
}