题解 | 链表相加(二)

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
    ListNode *reverseList(ListNode *head) {
        ListNode *p = head, *q, *last = nullptr;
        while(p) {
            q = p->next;
            p->next = last;
            last = p;
            p = q;
        }

        return last;
    }
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head1 ListNode类 
     * @param head2 ListNode类 
     * @return ListNode类
     */
    ListNode* addInList(ListNode* head1, ListNode* head2) {
        auto reverse_head1 = reverseList(head1);
        auto reverse_head2 = reverseList(head2);

        ListNode *p1 = reverse_head1, *p2 = reverse_head2;
        int carry = 0, add1, add2, sum, real_sum;
        ListNode *tail;
        ListNode *reverse_sum_head = nullptr;
        while(p1 || p2 || carry) {
            add1 = p1 ? p1->val : 0;
            add2 = p2 ? p2->val : 0;
            real_sum = add1 + add2 + carry;
            sum = real_sum % 10;
            carry = real_sum / 10;

            if(!reverse_sum_head) {
                reverse_sum_head = new ListNode(sum);
                tail = reverse_sum_head;
            } else {
                tail->next = new ListNode(sum);
                tail = tail->next;
            }
            if(p1) p1 = p1->next;
            if(p2) p2 = p2->next;
        }

        auto sum_head = reverseList(reverse_sum_head);
        return sum_head;
    }
};

模拟加法时发现是从链表尾部开始加，因此考虑将两个链表逆序，然后模拟竖式加法过程，模拟完之后再将结果链表逆序。易错点：考虑最后一个进位