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
给定两个由链表形式保存的非负整数，保存方式为高位在前，每个节点保存一位。将两个数相加并返回其链表形式。
可假定两个数最高位不含有0，除数本身是0的情况。
进阶：若不允许改变输入的形式将如何？换言之是不允许翻转链表。
思路：
简单思路是翻转链表，然后各位相加再将结果翻转过来即可。
进阶要求不能改动输入的链表，可采用以下做法：
- 使用栈来实现翻转功能
- 使用其他数据结构，如Vector来存储数据，实现当前位的高位的快速定位
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));
}
};
