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
| class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
l1 = reverse(l1);
l2 = reverse(l2);
ListNode dummy = new ListNode(1), ptr = dummy;
int carry = 0;
while (l1 != null || l2 != null || carry != 0) {
int l1Val = 0, l2Val = 0, sum = 0;
if (l1 != null) {
l1Val = l1.val;
}
if (l2 != null) {
l2Val = l2.val;
}
sum = l1Val + l2Val + carry;
int currDigit = sum % 10;
carry = sum / 10;
ptr.next = new ListNode(currDigit);
if (l1 != null) {
l1 = l1.next;
}
if (l2 != null) {
l2 = l2.next;
}
ptr = ptr.next;
}
return reverse(dummy.next);
}
private ListNode reverse(ListNode head) {
ListNode prev = null, curr = head;
while (curr != null) {
ListNode next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
return prev;
}
}
|
先反转再加就完事儿了.
时间复杂度: O(L1 + L2) reverse + 相加(需要遍历两个链表)
空间复杂度: O(L1) L1表示长的那个链表.
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
| class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
int l1Length = 0, l2Length = 0;
ListNode ptr = l1;
while (ptr != null) {
ptr = ptr.next;
l1Length += 1;
}
ptr = l2;
while (ptr != null) {
ptr = ptr.next;
l2Length += 1;
}
ptr = l1;
ListNode ptr2 = l2;
if (l1Length >= l2Length) {
for (int i = 0; i < l1Length - l2Length; i++) {
ptr = ptr.next;
}
while (ptr != null) {
ptr.val = ptr.val + ptr2.val;
ptr = ptr.next;
ptr2 = ptr2.next;
}
} else {
for (int i = 0; i < l2Length - l1Length; i++) {
ptr2 = ptr2.next;
}
while (ptr2 != null) {
ptr2.val = ptr.val + ptr2.val;
ptr = ptr.next;
ptr2 = ptr2.next;
}
}
Deque<ListNode> nodes = new ArrayDeque<>();
int carry = 0;
ptr = l1Length >= l2Length ? l1 : l2;
while (ptr != null) {
nodes.offerLast(ptr);
ptr = ptr.next;
}
while (!nodes.isEmpty()) {
ListNode currNode = nodes.pollLast();
int sum = carry + currNode.val;
int currDigit = sum % 10;
carry = sum / 10;
currNode.val = currDigit;
}
ListNode ans = null;
if (carry != 0) {
ans = new ListNode(carry);
ans.next = l1Length >= l2Length ? l1 : l2;
return ans;
} else {
return l1Length >= l2Length ? l1 : l2;
}
}
}
|
这个是不reverse. 先求两个链表的长度, 然后让长的链表的指针先走, 走到和短的链表的开头平齐. 之后把值加到长的链表上. 之后把长的链表的nodes压到栈里面. 挨个算carry和当前的digit因为这一位可能相加超过9. 到最后一个node处理完后, 如果carry还有值, 那么我们需要额外new一个新node指向长链表的表头. 否则就直接返回长的链表.
这个做法感觉很鸡肋, 算是follow up.
时间复杂度: O(4L1 + 2L2) L1和L2分别是两个链表的长度, L1表示长的那个. 计算两个链表的长度是L1 + L2, 把两个链表加起来是L1 + L2, 把长链表的node压入栈是L1, 出栈是L1.
空间复杂度: O(L1) 因为用了栈, L1表示长的那个.
