题解 | NO.11#链表相加(二)#3.6

/**
 * struct ListNode {
 *  int val;
 *  struct ListNode *next;
 *  ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
#include <cstddef>
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param head1 ListNode类
     * @param head2 ListNode类
     * @return ListNode类
     */
    struct ListNode* Reverse(struct ListNode* head) {
        if (head == NULL)
            return NULL;
        struct ListNode* cur = head;
        struct ListNode* pre = NULL;
        struct ListNode* temp = NULL;
        while (cur != NULL) {
            temp = cur->next;
            cur->next = pre;
            pre = cur;
            cur = temp;
        }
        return pre;
    }

    ListNode* addInList(ListNode* head1, ListNode* head2) {
        // 任意一个链表为空，返回另一个
        if(head1 == NULL)
            return head2;
        if(head2 == NULL)
            return head1;
        //反转两个链表
        head1 = Reverse(head1);
        head2 = Reverse(head2);
        //添加表头
        ListNode* res = new ListNode(-1);
        ListNode* head = res;
        //进位符号
        int carry = 0;
        //只要某个链表还有或者进位还有
        while(head1 != NULL || head2 != NULL || carry != 0){
            //链表不空则取其值
            int val1 = head1 == NULL ? 0 : head1->val;
            int val2 = head2 == NULL ? 0 : head2->val;
            //相加
            int temp = val1 + val2 + carry;
            //获取进位
            carry = temp / 10;
            temp %= 10;
            //添加元素
            head->next = new ListNode(temp);
            head = head->next;
            //移动下一个
            if(head1 != NULL)
                head1 = head1->next;
            if(head2 != NULL)
                head2 = head2->next;
        }
        //结果翻转过来
        return Reverse(res->next);
    }
};