假设链表中每一个节点的值都在 0 - 9 之间，那么链表整体就可以代表一个整数。

给定两个这种链表，请生成代表两个整数相加值的结果链表。

数据范围：0≤n,m≤1000000，链表任意值 0≤val≤9
要求：空间复杂度 O(n)，时间复杂度O(n)

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

# 示例1
输入：[9,3,7],[6,3]
返回值：{1,0,0,0}
说明：如题面解释

# 示例2
输入： [0],[6,3]
返回值：{6,3}

1≤n, m≤106
0≤ai, bi≤9

/**
 * struct ListNode {
 *  int val;
 *  struct ListNode *next;
 * };
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */

/**
 * 
 * @param head1 ListNode类 
 * @param head2 ListNode类 
 * @return ListNode类
 */

struct ListNode * reverseListnode(struct ListNode *head) {
    struct ListNode  *p, *q, *temp;
    if(head ==NULL) return NULL;
    if(head->next == NULL) return head;
    p = head;
    q = head->next;
    head->next = NULL;
    while(q != NULL) {
        temp = q->next;
        q->next = p;
        p = q;
        q = temp;
    }
    return p;
}

struct ListNode* addInList(struct ListNode* head1, struct ListNode* head2 ) {
    // write code here
    if(head1 == NULL && head2 == NULL) return NULL;
    struct ListNode *tail1, *tail2;
    tail1 = reverseListnode(head1);
    tail2 = reverseListnode(head2);
    int flag=0;
    struct ListNode  *p, *q, *head, *temp;
    p = tail1;
    q = tail2;
    temp = NULL;
    while(p != NULL && q != NULL) {
        head = (struct ListNode *) malloc(sizeof(struct ListNode));
        head->val = p->val + q->val;
        if(flag) {
            head->val ++;
            flag = 0;
        }
        if(head->val > 9) {
            head->val = head ->val -10;
            flag = 1;
        }
        head->next = temp;
        temp = head;
        p = p->next;
        q = q->next;
    }
    while(p != NULL) {
        head = (struct ListNode *) malloc(sizeof(struct ListNode));
        head->val = p->val;
        if(flag) {
            head->val ++;
            flag = 0;
        }
        if(head->val > 9) {
            head->val = head ->val -10;
            flag = 1;
        }
        head->next = temp;
        temp = head;
        p = p->next;
    }
    while(q != NULL) {
        head = (struct ListNode *) malloc(sizeof(struct ListNode));
        head->val = q->val;
        if(flag)  {
            head->val ++;
            flag = 0;
        }
        if(head->val > 9) {
            head->val = head ->val -10;
            flag = 1;
        }
        head->next = temp;
        temp = head;
        q = q->next;
    }
    if(flag)  {
        head = (struct ListNode *) malloc(sizeof(struct ListNode));
        head->val = 1;
        head->next = temp;
    }
    tail1->next = NULL;
    tail2->next = NULL;
    return head;
}