Question
给定两个采用链表表示的非负整数，数字采用逆序存储在每一个节点中，加和这两个数并以链表形式返回.
Solution
直接遍历两个链表，存储好商数，注意判断链表非空，以及最后可能需要额外添加一个节点，还有就是语法了Orz(c++的new，指针的.和->，不要轻易尝试&).
- Time complexity: $O(max(m,n))$. 这里$m$和$n$分别表示$l1$和$l2$的长度.
- Space complexity: $O(max(m,n))$.
Add-Two-Numbers
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
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
int r = l1->val + l2->val;
int quotient = r / 10;
ListNode *result = new ListNode(r % 10);
ListNode *current = result;
l1 = l1->next;
l2 = l2->next;
while (l1 && l2) {
r = l1->val + l2->val + quotient;
quotient = r / 10;
ListNode *newNode = new ListNode(r % 10);
current->next = newNode;
current = current->next;
l1 = l1->next;
l2 = l2->next;
}
if (l1 || l2) {
while (l1) {
r = l1->val + quotient;
quotient = r / 10;
current->next = new ListNode(r % 10);
current = current->next;
l1 = l1->next;
}
while (l2) {
r = l2->val + quotient;
quotient = r / 10;
current->next = new ListNode(r % 10);
current = current->next;
l2 = l2->next;
}
}
if (quotient != 0) {
current->next = new ListNode(quotient);
}
return result;
}