题解 | 链表相加(二)

给了我们两个链表，由高位到低位的存储了两个整数。我们需要返回一个新链表，内容是两个链表对于数字的和。

解法：我们只需要模拟竖式加法的过程即可。但是我们无法直接访问链表的尾部，所以我们先对两个链表进行逆置，然后对应位置相加，最后再将结果逆置回来即可。下面是具体步骤：

1.逆置链表：逆置链表可以使用双指针/头插法，这里我们采取头插法的方式逆置链表。首先创建一个虚拟头节点，然后遍历原链表，将原链表的每个节点都插到虚拟头节点的后面。

2.遍历两个逆序链表，记录对应位置的和，并创建新节点采取头插法插入到一个虚拟头节点后，这样就可以避免最后的逆置。在创建新节点后，里面的值是该位置和的个位数，同时还要更新进位，给下一位计算。

3.最后将创建的虚拟头节点给释放掉。

class Solution 
{
public:
    ListNode* addInList(ListNode* head1, ListNode* head2) 
    {
        if((head1 == nullptr && head2 == nullptr) || (head1 == nullptr && head2)) return head2;
        if(head1 && head2 == nullptr) return head1;

        // 1.先将原链表进行逆置 
        // 头插法
        ListNode* newhead1 = new ListNode(0);
        ListNode* newhead2 = new ListNode(0);
        while(head1 || head2)
        {
            if(head1)
            {
                ListNode* next = head1->next;
                head1->next = newhead1->next;
                newhead1->next = head1;
                head1 = next;
            }

            if(head2)
            {
                ListNode* next = head2->next;
                head2->next = newhead2->next;
                newhead2->next = head2;
                head2 = next;
            }
        }

        // 2.同时遍历两个逆置链表，进行加法运算
        ListNode* ret = new ListNode(0);
        ListNode* cur1 = newhead1->next;
        ListNode* cur2 = newhead2->next;
        int carry = 0;
        while(cur1 || cur2 || carry)
        {
            carry += cur1?cur1->val:0;
            carry += cur2?cur2->val:0;
            ListNode* newNode = new ListNode(carry%10);
            carry /= 10;

            // 头插法，将和链表逆置回来
            newNode->next = ret->next;
            ret->next = newNode;

            cur1 = cur1?cur1->next:nullptr;
            cur2 = cur2?cur2->next:nullptr;
        }

        cur1 = ret->next;
        delete ret;
        delete newhead1;
        delete newhead2;

        return cur1;
    }
};