题解 | 链表相加(二)

/**
 * struct ListNode {
 *  int val;
 *  struct ListNode *next;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param head1 ListNode类
 * @param head2 ListNode类
 * @return ListNode类
 */
struct ListNode* addInList(struct ListNode* head1, struct ListNode* head2 ) {
    //思路（由于结点数量最大1000000个，因此不可用数字转换方法）
    //将两个链表逆转，方便从低位开始计算
    //从二者低位开始相加，每次记录是否满10，若满10则在二者的下一位计算中加入1
    //创建新链表放置结果

    struct ListNode* nodeTmp = NULL;
    struct ListNode* reverse1Node = NULL;
    struct ListNode* reverse2Node = NULL;
    struct ListNode reverseHead1Node = { .next = head1 };
    struct ListNode reverseHead2Node = { .next = head2 };
    struct ListNode resultHeadNode = { .next = NULL };
    int numberTmp = 0;
    char upToTen = 0;

    //逆转链表1
    nodeTmp = head1->next;
    while (head1->next) {
        head1->next = nodeTmp->next;
        nodeTmp->next = reverseHead1Node.next;
        reverseHead1Node.next = nodeTmp;
        nodeTmp = head1->next;
    }
    //逆转链表2
    nodeTmp = head2->next;
    while (head2->next) {
        head2->next = nodeTmp->next;
        nodeTmp->next = reverseHead2Node.next;
        reverseHead2Node.next = nodeTmp;
        nodeTmp = head2->next;
    }

    //计算生成结果链表
    reverse1Node = reverseHead1Node.next;
    reverse2Node = reverseHead2Node.next;
    while (reverse1Node != NULL || reverse2Node != NULL) {
        if (reverse1Node != NULL && reverse2Node != NULL) {
            //将链表结点从开到尾，两两相加
            numberTmp = reverse1Node->val + reverse2Node->val;
            //移动链表指针
            reverse1Node = reverse1Node->next;
            reverse2Node = reverse2Node->next;
        } else {
            //其中一个链表已经遍历结束，则只计算另一链表的剩余结点
            if (reverse1Node == NULL) {
                numberTmp = 0 + reverse2Node->val;
                reverse2Node = reverse2Node->next; // 移动链表指针
            } else if (reverse2Node == NULL) {
                numberTmp = reverse1Node->val + 0;
                reverse1Node = reverse1Node->next; // 移动链表指针
            }
        }
        //创建新结点
        numberTmp += upToTen;
        nodeTmp = (struct ListNode*)malloc(sizeof(struct ListNode));
        nodeTmp->val = numberTmp % 10;
        nodeTmp->next = resultHeadNode.next;
        resultHeadNode.next = nodeTmp;
        //满十进一
        if (numberTmp > 9) {
            upToTen = 1;
        } else {
            upToTen = 0;
        }
    }
    //最后一次计算满十，需要增加一个结点
    if(upToTen == 1) {
        nodeTmp = (struct ListNode*)malloc(sizeof(struct ListNode));
        nodeTmp->val = 1;
        nodeTmp->next = resultHeadNode.next;
        resultHeadNode.next = nodeTmp;
    }
    return resultHeadNode.next;
}