LeetCode 02. Add Two Numbers
LeetCode 02. Add Two Numbers
🧩 PROBLEM - LeetCode 02. Add Two Numbers
LINK: https://leetcode.com/problems/add-two-numbers/description/
Given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of nodes is a single digit. Let’s sum two linked list.
Example.
[1]
Input: l1 = [2,4,3], l1 = [5,6,4]
Output: [7,0,8]
Explanation: 342 + 465 = 807
[2]
Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
Output: [8,9,9,9,0,0,0,1]
Constraints:
The number of nodes in each linked list is in the range [1, 100] 0 <= Node.val <= 9 It is guaranteed that the list represents a number that does not have leading zeros
Problem anaylsis
- Convert range 100 to a datatype -> impossible
- Should sum digit by digit
- Check the linked list structure -> Singly Linked List, Not Doubly Linked List
- nums.length -> time complex should be under 0~3ms
- nums.length -> space complex should be O(n)
Miss Check list
- Not need to get reverse the digit of linked list.
- Order of link is order of sum.
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
# Missunderstand about not to need to get reverse linked list.
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2)
{
int i32Size1 = 1;
int i32Size2 = 1;
{
ListNode* l1Next = l1;
ListNode* l2Next = l2;
while (1)
{
if (l1Next = l1Next->next)
++i32Size1;
else
break;
}
while (1)
{
if (l2Next = l2Next->next)
++i32Size2;
else
break;
}
}
ListNode* lnHigh = nullptr;
ListNode* lnLow = nullptr;
int i32SizeHigh, i32SizeLow;
{
if (i32Size1 >= i32Size2)
{
lnHigh = l1;
lnLow = l2;
i32SizeHigh = i32Size1;
i32SizeLow = i32Size2;
}
else
{
lnHigh = l2;
lnLow = l1;
i32SizeHigh = i32Size2;
i32SizeLow = i32Size1;
}
}
int i32DiffDigit = i32SizeHigh - i32SizeLow;
std::vector<int> vctHigh;
std::vector<int> vctLow;
std::vector<int> vctUpper;
vctHigh.resize(i32SizeHigh, 0);
vctLow.resize(i32SizeLow, 0);
ListNode* lnCursor = nullptr;
lnCursor = lnHigh;
for (int i = 0; i < i32SizeHigh; ++i)
{
vctHigh[i] = lnCursor->val;
lnCursor = lnCursor->next;
}
lnCursor = lnLow;
for (int i = 0; i < i32SizeLow; ++i)
{
vctLow[i] = lnCursor->val;
lnCursor = lnCursor->next;
}
int i32Upper = 0;
for (int i = 0; i < i32SizeLow; ++i)
{
int i32Value = vctLow[i] + vctHigh[i] + i32Upper;
i32Upper = i32Value / 10;
vctHigh[i] = i32Value % 10;
}
for (int i = i32SizeLow; i < i32SizeHigh; ++i)
{
int i32Value = vctHigh[i] + i32Upper;
i32Upper = i32Value / 10;
vctHigh[i] = i32Value % 10;
}
ListNode* lnResult = new ListNode;
ListNode* lnResultCursor = lnResult;
lnResultCursor->val = vctHigh[0];
lnResultCursor->next = nullptr;
for (int i = 1; i < i32SizeHigh; ++i)
{
ListNode* lnResultNext = new ListNode;
lnResultNext->val = vctHigh[i];
lnResultNext->next = nullptr;
lnResultCursor->next = lnResultNext;
lnResultCursor = lnResultNext;
}
if (i32Upper > 0)
{
ListNode* lnResultNext = new ListNode;
lnResultNext->val = i32Upper;
lnResultNext->next = nullptr;
lnResultCursor->next = lnResultNext;
}
return lnResult;
}
};
More Clear Code
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
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2)
{
ListNode* ndResult = new ListNode;
ListNode* ndCursor = ndResult;
int i32Upper = 0;
int i32Digit = 0;
ndCursor->val = (l1->val + l2->val) % 10;
ndCursor->next = nullptr;
i32Upper = (l1->val + l2->val) / 10;
l1 = l1->next;
l2 = l2->next;
while (1)
{
if (!l1 && !l2)
break;
i32Digit = 0;
i32Digit += i32Upper;
if (l1)
i32Digit += l1->val;
if (l2)
i32Digit += l2->val;
ListNode* ndNext = new ListNode;
ndNext->val = i32Digit % 10;
i32Upper = i32Digit / 10;
ndNext->next = nullptr;
ndCursor->next = ndNext;
ndCursor = ndCursor->next;
if (l1)
l1 = l1->next;
if (l2)
l2 = l2->next;
}
if (i32Upper > 0)
{
ListNode* ndNext = new ListNode;
ndNext->val = i32Upper;
ndNext->next = nullptr;
ndCursor->next = ndNext;
ndCursor = ndCursor->next;
}
return ndResult;
}
};
-> Problem is quite simple. But Should be understanding linked list structure and step by step.
Anaylsis
- CHECK SCOPE -> INPUT SIZE
- Under Hundred: O($2^n$)
- Under thousand : O($n^2$)
- Under 10K: O(N $\log{N}$)
- Under 1M ~ over: O( $\log{n}$)
- COMPLEXITY
- Time complexity
- Space complexity
- Check Valid DataType
- Overflow
- SIMULATION
- Check test case by myself
- Compare with other people solutions
This post is licensed under CC BY 4.0 by the author.