445.两数相加(顺) II && 002(逆)

1.445题目

image-20200623182854483

2.类型:链表 && 栈

正序的数字链表,求和时希望从个位开始算(逆序算),所以应该想到利用 (FILO)

3.与002区别:

  • 002采用的是直接逆序存储的数字链表,所以可以直接从数字的尾巴开始求和,另外增加一个 进位标志符号 就可以;


4.代码 Java

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
import java.util.*;

public class twoSum_445 {
public static void main(String[] args) {
}
public class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
Stack<Integer> stack1 = new Stack<>();
Stack<Integer> stack2 = new Stack<>();
while( l1 != null){
stack1.push(l1.val);
l1 = l1.next;
}
while( l2 != null){
stack2.push(l2.val);
l2 = l2.next;
}

int carry = 0;//进位符号
ListNode head = null;
while(!stack1.empty() || !stack2.empty()){
int sum = carry;
sum += stack1.isEmpty()? 0:stack1.pop();
sum += stack1.isEmpty()? 0:stack2.pop();
ListNode node = new ListNode(sum % 10);
node.next = head;
head = node;
carry = sum / 10;
}
return head;
}

}

5.比较 002 代码:

image-20200623182835143

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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
import java.util.*;

public class twoSum_002 {
public static void main(String[] args) {
}
public class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}

//这份写的更漂亮,更优美,学习一个!
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
int carry = 0;
ListNode dummyHead = new ListNode(0);

ListNode p = l1, q = l2, curr = dummyHead;
while(p != null || q!= null){
int x = (p != null)? p.val : 0;
int y = (q != null)? q.val : 0;
int sum = x + y + carry;
carry = sum / 10;
curr.next = new ListNode(sum % 10);
curr = curr.next;
if(p != null) p = p.next;
if(q != null) q = q.next;
}
if(carry > 0){
curr.next = new ListNode(carry);
}
return dummyHead.next;
}

//这个我自己写的,改了好多地方才对,细节很多
public ListNode addTwoNumber_HSJ(ListNode l1, ListNode l2){
int carry = 0;
ListNode head = new ListNode(0);
ListNode curr = head;

while( l1 != null || l2 != null){//细节,不是 l1.next !!!
int sum = 0;
sum += carry;

if( l1 != null)
sum += l1.val;
if( l2 != null)
sum += l2.val;

ListNode node = new ListNode(0);

carry = sum / 10;
node.val = sum % 10;
curr.next = node;
curr = node;
// node.next = head;
// head = node;

if(l1 != null) l1 = l1.next;
if(l2 != null) l2 = l2.next;

}
if(carry > 0){//细节!
curr.next = new ListNode(carry);
}
return head.next;

}

}