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

1、将两个链表翻转，方便相加；

2、需要考虑相加时的进位问题，以及链表移动到尾部时的情况；

3、两个链表都移动到尾部后，还需要考虑最后是否有进位的问题，如果有进位则需要多增加一个结点，若无则不需要增加。

时间复杂度：o(n)

空间复杂度：o(n)

class Solution {
 public:
    ListNode* reverse(ListNode* head) {
        ListNode* ptemp = nullptr;
        ListNode* pnode = head;

        while (pnode != nullptr) {
            ListNode* pnext = pnode->next;
            pnode->next = ptemp;
            ptemp = pnode;
            pnode = pnext;
        }
        return ptemp;
    }

    ListNode* addInList(ListNode* head1, ListNode* head2) {
        //特殊情况处理
        if (head1 == nullptr)
            return head2;
        if (head2 == nullptr)
            return head1;
		//先将两个链表翻转，方便相加
        ListNode* phead1 = reverse(head1);
        ListNode* phead2 = reverse(head2);
	  	//设置表头
        ListNode* res = new ListNode(-1);
        ListNode* ptemp = res;

        int add = 0;
        while (phead1 != nullptr || phead2 != nullptr) {
            int num1 = 0;
            int num2 = 0;
            if (phead1 != nullptr) {
                num1 = phead1->val;
            } 
            if (phead2 != nullptr) {
                num2 = phead2->val;
            } 
            
            int sum = num1 + num2;

            ptemp->next = new ListNode((sum + add) % 10 );
            add = (sum + add) / 10;

            ptemp = ptemp->next;
		  	//如果有链表已经到了尾部，则不再移动
            if(phead1 != nullptr)
                phead1 = phead1->next;
            if(phead2 != nullptr)
                phead2 = phead2->next;
        }
	  	//如果到相加到了链表的最后一位了，还需判断是否有进位
        if(add == 0) {
            ptemp->next = nullptr;
        } else {
            ptemp->next = new ListNode(add);
            ptemp->next->next = nullptr;
        }

        return reverse(res->next);
    }
};