【LeetCode】Add Two Numbers

题目如下

You are given two non-empty linked lists representing two non-negative integers. 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.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example:

1
2
3
4
> Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
> Output: 7 -> 0 -> 8
> Explanation: 342 + 465 = 807.
>

思路

这道题目描述是两个不为空节点个数不一定相等的链表,对应位置的节点元素进行相加,如果相加大于10,则取个位数,然后让next节点总数+1。思路是遍历两个链表,直到两个链表节点的next元素节点为null,则结束循环遍历。每次循环的总数等于 l1.val + l2.val + lastExtra。最后判断lastExtra是否为1,是则增加尾节点。两个陷阱,一个是两个链表的节点个数不一定相同,另一个是最后节点相加可能会大于10。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
public static class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}

private static ListNode solution(ListNode l1 , ListNode l2){
ListNode resultFirstNode = null,lastNode = null ;
int lastExtra = 0;
for(ListNode currentFirst = l1, currentSecond = l2
; Objects.nonNull(currentFirst) || Objects.nonNull(currentSecond)
; currentFirst = currentFirst.next , currentSecond = currentSecond.next){
if( Objects.isNull(currentFirst) ){
currentFirst = new ListNode(0);
}
if( Objects.isNull(currentSecond) ){
currentSecond = new ListNode(0);
}
//总数 = 左节点的值 + 右节点的值 + 上一个总数进1位的值
int sum = currentFirst.val + currentSecond.val + lastExtra;
//判断是否要进1
lastExtra = (sum >= 10) ? 1 : 0;
//记录output链表节点的值
ListNode currentNode = new ListNode(sum%10);
if( lastNode != null ){
lastNode.next = currentNode;
}
lastNode = currentNode;
if( resultFirstNode == null ){
resultFirstNode = lastNode;
}
}
//判断最后是否需要增加尾节点
if( lastExtra == 1 ){
lastNode.next = new ListNode(lastExtra);
}
return resultFirstNode;
}

Submission Detail

提交结果


评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×