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
給定兩個由鏈表形式保存的非負整數(shù)，保存方式為高位在前拟枚，每個節(jié)點保存一位。將兩個數(shù)相加并返回其鏈表形式。
可假定兩個數(shù)最高位不含有0琢融，除數(shù)本身是0的情況严蓖。
進階：若不允許改變輸入的形式將如何优俘？換言之是不允許翻轉(zhuǎn)鏈表。
思路：
簡單思路是翻轉(zhuǎn)鏈表矛缨，然后各位相加再將結(jié)果翻轉(zhuǎn)過來即可。
進階要求不能改動輸入的鏈表帖旨，可采用以下做法：
- 使用棧來實現(xiàn)翻轉(zhuǎn)功能
- 使用其他數(shù)據(jù)結(jié)構(gòu)箕昭，如Vector來存儲數(shù)據(jù)，實現(xiàn)當(dāng)前位的高位的快速定位
class Solution {
vector<int> convertToVector(ListNode *head) {
vector<int> res;
while (head) {
res.push_back(head->val);
head = head->next;
}
return res;
}
ListNode* addTwoVector(vector<int> v1, vector<int> v2) {
ListNode *dummy = new ListNode(0), *node = NULL;
int i = v1.size() - 1, j = v2.size() - 1, sum = 0;
while (j >= 0 || i >= 0 || sum) {
if (i >= 0) sum += v1[i--];
if (j >= 0) sum += v2[j--];
node = new ListNode(sum % 10);
sum /= 10;
node->next = dummy->next;
dummy->next = node;
}
return dummy->next;
}
public:
ListNode* addTwoNumbers(ListNode *l1, ListNode *l2) {
return addTwoVector(convertToVector(l1), convertToVector(l2));
}
};
