leetcode-java/src/AddTwoNumbersII445.java at master · fluency03/leetcode-java · GitHub

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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
/**
 * You are given two non-empty linked lists representing two non-negative
 * integers. The most significant digit comes first 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.
 *
 * Follow up:
 * What if you cannot modify the input lists? In other words, reversing the
 * lists is not allowed.
 *
 * Example:
 *
 * Input: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
 * Output: 7 -> 8 -> 0 -> 7
 */

/**
 * Definition for singly-linked list.
 * public class ListNode {
 * int val;
 * ListNode next;
 * ListNode(int x) { val = x; }
 * }
 */

publicclassAddTwoNumbersII445 {
publicListNodeaddTwoNumbers(ListNodel1, ListNodel2) {
Stack<Integer> s1 = newStack<>();
Stack<Integer> s2 = newStack<>();

while (l1 != null && l2 != null) {
s1.push(l1.val);
l1 = l1.next;
s2.push(l2.val);
l2 = l2.next;
 }
while (l1 != null) {
s1.push(l1.val);
l1 = l1.next;
 }
while (l2 != null) {
s2.push(l2.val);
l2 = l2.next;
 }

ListNodedummy = newListNode(0);
ListNodep = dummy;
intcarry = 0;
while (!s1.isEmpty() && !s2.isEmpty()) {
intsum = s1.pop() + s2.pop() + carry;
ListNodecurr = newListNode(sum % 10);
curr.next = p.next;
p.next = curr;
carry = sum / 10;
 }
while (!s1.isEmpty()) {
intsum = s1.pop() + carry;
ListNodecurr = newListNode(sum % 10);
curr.next = p.next;
p.next = curr;
carry = sum / 10;
 }
while (!s2.isEmpty()) {
intsum = s2.pop() + carry;
ListNodecurr = newListNode(sum % 10);
curr.next = p.next;
p.next = curr;
carry = sum / 10;
 }
if (carry != 0) {
ListNodecurr = newListNode(carry);
curr.next = p.next;
p.next = curr;
 }

returndummy.next;
 }


publicListNodeaddTwoNumbers2(ListNodel1, ListNodel2) {
ListNodell1 = reverseList(l1);
ListNodell2 = reverseList(l2);

returnreverseList(addTwoNumbers0(ll1, ll2));
 }

publicListNodeaddTwoNumbers0(ListNodel1, ListNodel2) {
ListNodedummy = newListNode(0);
ListNodep = dummy;
intcarry = 0;
while (l1 != null || l2 != null) {
inta = l1 == null ? 0 : l1.val;
intb = l2 == null ? 0 : l2.val;
intsum = a + b + carry;
ListNoden = newListNode(sum%10);
p.next = n;
p = p.next;
carry = sum/10;
l1 = l1 == null ? null : l1.next;
l2 = l2 == null ? null : l2.next;
 }

if (carry != 0) p.next = newListNode(carry);

returndummy.next;
 }

publicListNodereverseList(ListNodehead) {
if (head == null || head.next == null) returnhead;

ListNodedummy = newListNode(0);
ListNodetail = null;

while (head != null) {
ListNodet = head;
head = head.next;
tail = dummy.next;
dummy.next = t;
dummy.next.next = tail;
 }

returndummy.next;
 }

}