2. 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 contains a single digit. Add the two numbers and return the sum as a linked list.

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

递归,每次递归时建立root的next节点,然后将root移动到root.next。
计算两个节点的和并填入root节点。每次计算时需要计算是否进位。
递归两个节点的next节点,并将carry传入。
当一个节点为null时,只递归和计算另一个节点。
当两个节点为null时,如果有carry需要将其放入新节点,如果没有则返回。

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
39
40
41
42
43
44
45
46
47
48
49
50
51
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode root = new ListNode();
addTwo(l1,l2,root,0);
return root.next;
}

private void addTwo(ListNode l1, ListNode l2, ListNode root, int carry){
if(l1 == null && l2 == null && carry == 0){
return;
}
else if(l1 == null && l2 == null){
root.next = new ListNode();
root = root.next;
root.val = carry;
return;
}
else if(l1 == null){
root.next = new ListNode();
root = root.next;
root.val = (l2.val + carry) % 10;
carry = (l2.val + carry) / 10;
addTwo(null, l2.next, root, carry);
return;
}
else if(l2 == null){
root.next = new ListNode();
root = root.next;
root.val = (l1.val + carry) % 10;
carry = (l1.val + carry) / 10;
addTwo(null, l1.next, root, carry);
return;
}
root.next = new ListNode();
root = root.next;
root.val = (l1.val + l2.val + carry) % 10;
carry = (l1.val + l2.val + carry) / 10;

addTwo(l1.next, l2.next, root, carry);
}
}
Author

Xander

Posted on

2022-04-25

Updated on

2022-04-25

Licensed under

Comments