题目描述

给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。

如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。

您可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例：

输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807

C语言代码

struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2){
    int flag = 0, x1 = 0, x2 = 0,a,b;
    struct ListNode *p1=l1,*p2=l2,*b1 = l1, *b2 = l2,*f1 = l1,*f2 = l2, *p3;
    if(l1==NULL&&l2==NULL)
        return NULL;
    
    while(p1!=NULL&&p2!=NULL){  // 判断两个链表的长度
        p1 = p1->next;
        p2 = p2->next;
        if(p1!=NULL){
            x1 ++;
        }
        if(p2!=NULL){
            x2 ++;
        } 
    }    
    
    while(l1!=NULL && l2!= NULL){  // 当其中一个链表已经到达最高位，则进入下一步
        a = l1->val;
        b = l2->val;
        
        if(x1 >= x2)
            if(flag == 1){
                l1->val = (a + b + 1) % 10;
                a += 1; // 此处注意
            }
            else
                l1->val = (a + b) % 10;            
        else
            if(flag == 1){
                l2->val = (a + b + 1) % 10;
                b += 1; // 此处注意
            }
            else
                l2->val = (a + b) % 10;      
        if(a + b >= 10)
            flag = 1;
        else
            flag = 0;       
        l1 = l1->next;
        l2 = l2->next;       
    } 
    
    CD:if(flag == 1){  // 一个链表到达最高位后的计算
        if(x1>=x2)
            if(l1 == NULL){              
                p3 = (struct ListNode *)malloc(sizeof(struct ListNode));
                p3->val = 1;
                p3->next =NULL;
                while(f1->next != NULL)
                    f1 = f1->next;
                f1->next = p3;
                f1 = p3;
            }
            else
            {
                l1->val += 1;
                if(l1->val >= 10){
                    l1->val = l1->val%10;                    
                    l1 = l1->next;
                    goto CD;
                }
            }
        else
            if(l2 == NULL){
                p3 = (struct ListNode *)malloc(sizeof(struct ListNode));
                p3->val = 1;
                p3->next =NULL;
                while(f2->next != NULL)
                    f2 = f2->next;
                f2->next = p3;
                f2 = p3;
            }
            else
            {
                l2->val += 1;               
                if(l2->val >= 10){
                    l2->val = l2->val%10;                 
                    l2 = l2->next;
                    goto CD;
                }
            }
        
    if(x1 >= x2)
        return b1;
    else
        return b2;
}

代码描述

两个链表数字相加，其中一个链表到达最高位后，进行其他高位的运算。如果最高位还需要进位，用动态分配给进位的数，此时最高位只可能是1。代码用时较长，可能是goto语句用时长。

执行用时 : 44 ms, 在Add Two Numbers的C提交中击败了67.49% 的用户
内存消耗 : 8.2 MB, 在Add Two Numbers的C提交中击败了99.84% 的用户

优秀代码

struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2){
    int num, temp = 0;

    struct ListNode * outputNode = (struct ListNode *)malloc(sizeof(struct ListNode));
    outputNode -> next = NULL;
    struct ListNode * tail = outputNode;
    
    while(l1 || l2){
        num = 0;
        if(l1 != NULL){
            num += l1->val;
            l1 = l1->next;
        }
        
        if(l2 != NULL){
            num += l2->val;
            l2 = l2->next;
        }
        
        num += temp;
        temp = 0;
        
        if(num >= 10){
            num %= 10;
            temp = 1;
        }
        
        tail -> val = num;
        
        if(l1 || l2){
            struct ListNode* newNode = (struct ListNode*)malloc(sizeof(struct ListNode));
            newNode -> next = NULL;
            tail -> next = newNode;
            tail = tail -> next;
        }
    }
    
    if(temp){
        struct ListNode* newNode = (struct ListNode*)malloc(sizeof(struct ListNode));
        newNode -> next = NULL;
        tail -> next = newNode;
        tail = tail -> next;
        tail -> val = temp;
    }
    
    return outputNode;
}