优点就是空间复杂度为O(1)，最坏情况下只需要额外开辟1个node的空间保存最高位的进1。
时间复杂度是O(n)，翻转两个链表O(n)，相加，注意，相加之后链表1和2对应位置保留相同的结果，
然后如果链表1长，就用链表1接着加，反之亦然，加完复杂度O(max(n,m))



/**
 * struct ListNode {
 *    int val;
 *    struct ListNode *next;
 * };
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */
struct ListNode* reverse(struct ListNode* head)
{
    //翻转链表，头变尾，尾边头
    struct ListNode *p = NULL, *n, *t;
    //翻转第一个链表
    n = head;
    while(n != NULL)
    {
        t = n;
        n = n->next;
        t->next = p;
        p = t;
    }
    return p;
}


/**
 * 
 * @param head1 ListNode类 
 * @param head2 ListNode类 
 * @return ListNode类
 */
struct ListNode* addInList(struct ListNode* head1, struct ListNode* head2 ) {
    // write code here
    
    
    struct ListNode *p1, *p2, *new_head1, *new_head2;
    //翻转链表
    new_head1 = reverse(head1);
    new_head2 = reverse(head2);
    p1 = new_head1;
    p2 = new_head2;
    //开始相加
    int add = 0, flag = 0;//储存进位 和 哪个链表到头了
    while(p1 != NULL || p2 != NULL)
    {//最多只有一个是空的
        if(p1 == NULL)
        {
            flag = 2;
            add = add + p2->val;
            if(add >= 10)
            {
                p2->val = add % 10;
                add = 1;                
            }else{
                p2->val = add;
                add = 0;
            }
            p2 = p2->next;
        }else if(p2 == NULL){
            flag = 1;
            add = add + p1->val;
            if(add >= 10)
            {
                p1->val = add % 10;
                add = 1;                
            }else{
                p1->val = add;
                add = 0;
            }
            p1 = p1->next;
        }else{
            add = add + p1->val + p2->val;
            if(add >= 10)
            {
                p1->val = add % 10;
                p2->val = add % 10;
                add = 1;                
            }else{
                p1->val = add;
                p2->val = add;
                add = 0;
            }
            p1 = p1->next;
            p2 = p2->next;
        }
        
    }
    //p1,p2现在都为空 flag有3种状态，0,1,2，
    if(flag == 0)
    {//两个链表一样长
        if(add == 1)
        {
            struct ListNode *new_node = (struct ListNode*)malloc(sizeof(struct ListNode*));
            new_node->val = 1;
            new_node->next = NULL;
            head1->next = new_node;
            return reverse(new_head1);
        }else{
            return reverse(new_head1);
        }
    }else if(flag == 1)
    {// 链表1比链表2长
        if(add == 1)
        {
            struct ListNode *new_node = (struct ListNode*)malloc(sizeof(struct ListNode*));
            new_node->val = 1;
            new_node->next = NULL;
            head1->next = new_node;
            return reverse(new_head1);
        }else{
            return reverse(new_head1);
        }
    }else{//链表2比链表1长
        if(add == 1)
        {
            struct ListNode *new_node = (struct ListNode*)malloc(sizeof(struct ListNode*));
            new_node->val = 1;
            new_node->next = NULL;
            head2->next = new_node;
            return reverse(new_head2);
        }else{
            return reverse(new_head2);
        }
    }
//     return new_head1;
}