题解 | #链表相加(二)#

/**
 * struct ListNode {
 *  int val;
 *  struct ListNode *next;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param head1 ListNode类
 * @param head2 ListNode类
 * @return ListNode类
 */
#include <stdlib.h>
struct ListNode* addInList(struct ListNode* head1, struct ListNode* head2 ) {
    // write code here
    if (head1->next == NULL && head2->next == NULL) {  // 两个一位数相加
        head1->val = head1->val + head2->val;
        if (head1->val >= 10) {  // 需要进位
            head1->val = head1->val - 10;
            struct ListNode* p = (struct ListNode*)malloc(sizeof(struct ListNode));
            p->val = 1;
            p->next = head1;  // 头插法
            head1->next = NULL;
            return p;
        } else {  // 不需要进位
            return head1;
        }
    }
    struct ListNode* L1 = (struct ListNode*)malloc(sizeof(struct ListNode));
    L1->next = NULL;
    while (head1 != NULL) {  // 新建L1储存head1的翻转,L1带头结点
        struct ListNode* tmp = (struct ListNode*)malloc(sizeof(struct ListNode));
        tmp->val = head1->val;
        tmp->next = L1->next;
        L1->next = tmp;
        head1 = head1->next;
    }
    struct ListNode* L2 = (struct ListNode*)malloc(sizeof(struct ListNode));
    L2->next = NULL;
    while (head2 != NULL) {  // 新建L2储存head2的翻转,L2带头结点
        struct ListNode* tmp = (struct ListNode*)malloc(sizeof(struct ListNode));
        tmp->val = head2->val;
        tmp->next = L2->next;
        L2->next = tmp;
        head2 = head2->next;
    }
    int jinwei = 0;
    struct ListNode* L = (struct ListNode*)malloc(sizeof(struct ListNode));
    L->next = NULL;  // 新建L储存结果
    struct ListNode* LL1 = L1->next;  // LL1从L1的首元结点开始
    struct ListNode* LL2 = L2->next;  // LL2从L2的首元结点开始
    while (LL1 != NULL && LL2 != NULL) {
        struct ListNode* p = (struct ListNode*)malloc(sizeof(struct ListNode));
        // 新建结点p用来存放两个结点的和
        p->val = LL1->val + LL2->val + jinwei;
        if (p->val >= 10) {  // 两个结点的和需要进位
            p->val = p->val - 10;
            jinwei = 1;
            LL1 = LL1->next;
            LL2 = LL2->next;
        } else {
            jinwei = 0;
            LL1 = LL1->next;
            LL2 = LL2->next;
        }
        p->next = L->next;
        L->next = p;
    }
    // L1和L2可能位数相同,可能L1位数更多,可能L2位数更多
    if (LL1 == NULL && LL2 == NULL) {  // 位数相同
        if (jinwei == 0) {  // 最高位不用再进一位
            return L->next;
        } else {  // 最高位还要再进一位,新的最高位变为1
            struct ListNode* p = (struct ListNode*)malloc(sizeof(struct ListNode));
            p->val = 1;
            p->next = L->next;
            L->next = p;
            return L->next;
        }
    } else if (LL1 != NULL && LL2 == NULL) { // L1比L2长
        while (LL1 != NULL) {
            struct ListNode* p = (struct ListNode*)malloc(sizeof(struct ListNode));
            p->val = LL1->val + jinwei;  // L1的结点和进位数相加
            if (p->val >= 10) {  // 还是要进位,比如9+1
                p->val = p->val - 10;
                jinwei = 1;
                LL1 = LL1->next;
            } else {
                jinwei = 0;
                LL1 = LL1->next;
            }
            p->next = L->next;
            L->next = p;
        }
        if (jinwei == 0) {  // 最高位不用进位
            return L->next;
        } else {  // 最高位还要进位,新的最高位变为1
            struct ListNode* p = (struct ListNode*)malloc(sizeof(struct ListNode));
            p->val = 1;
            p->next = L->next;
            L->next = p;
            return L->next;
        }
    } else if (LL1 == NULL && LL2 != NULL) {  // L2比L1长
        while (LL2 != NULL) {
            struct ListNode* p = (struct ListNode*)malloc(sizeof(struct ListNode));
            p->val = LL2->val + jinwei;
            if (p->val >= 10) {
                p->val = p->val - 10;
                jinwei = 1;
                LL2 = LL2->next;
            } else {
                jinwei = 0;
                LL2 = LL2->next;
            }
            p->next = L->next;
            L->next = p;
        }
        if (jinwei == 0) {
            return L->next;
        } else {
            struct ListNode* p = (struct ListNode*)malloc(sizeof(struct ListNode));
            p->val = 1;
            p->next = L->next;
            L->next = p;
            return L->next;
        }
    }
    return L->next;
}