445. Add Two Numbers II 两数相加2

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的情况。
进阶：若不允许改变输入的形式将如何？换言之是不允许翻转链表。

思路：
简单思路是翻转链表，然后各位相加再将结果翻转过来即可。
进阶要求不能改动输入的链表，可采用以下做法：

1. 使用栈来实现翻转功能
2. 使用其他数据结构，如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));
    }
};