描述
假设链表中每一个节点的值都在 0 - 9 之间，那么链表整体就可以代表一个整数。
给定两个这种链表，请生成代表两个整数相加值的结果链表。
数据范围：0 \le n,m \le 10000000≤n,m≤1000000，链表任意值 0 \le val \le 90≤val≤9
要求：空间复杂度 O(n)O(n)，时间复杂度 O(n)O(n)

例如：链表 1 为 9->3->7，链表 2 为 6->3，最后生成新的结果链表为 1->0->0->0。

解题思路：
最自然的做法还是三次翻转：
链表1翻转
链表2翻转
逐位求和（注意进位）
结果翻转，内存O（1），复杂度O（n） 


/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */

class Solution {
public:
    /**
     * 
     * @param head1 ListNode类 
     * @param head2 ListNode类 
     * @return ListNode类
     */
    ListNode* reverseList(ListNode* head){
        ListNode *pre = new ListNode(0);
        pre->next = head;
        while(head->next != NULL){
            ListNode *tmp = head->next;
            head->next = tmp->next;
            tmp->next = pre->next;
            pre->next = tmp;
        }
        
        return pre->next;
    }
    
    ListNode* addInList(ListNode* head1, ListNode* head2) {
        // write code here
        ListNode* head11 = reverseList(head1);
        ListNode* head12 = reverseList(head2);
        ListNode* res = new ListNode(-1);
        ListNode* cur = res;
        bool addOne = false;
        while(head11 || head12){
            int num = 0;
            if(head11){
                num += head11->val;
            }
            if(head12){
                num += head12->val;
            }
            if(addOne){
                num += 1;
                addOne = false;
            }
            if(num > 9){
                addOne = true;
                num %= 10; 
            }
            
            ListNode* tmp;
            if(head11){
                head11->val = num;
                tmp = head11;
                head11 = head11->next;
            }
            
            if(head12){
                head12->val = num;
                tmp = head12;
                head12 = head12->next;
            }
    
            cur->next = tmp;
            cur = tmp;
        }
        
        if(addOne){
            ListNode *one = new ListNode(1);
            cur->next = one;
            cur = one;
        }
        
        return reverseList(res->next);
    }
};