题解 | #两个链表生成相加链表#

NC40 两个链表生成相加链表

题意分析：

将两个由链表所表示的数相加，求得结果。

题解一（反转链表后模拟相加）：

链表[9,3,7]和链表[6,3]相加。得到[1,0,0,0]。按照常规加法运算，低位与低位相加。由于我们无法确定哪个位置是低位，因此需要把链表反转后，模拟常规加法运算即可，最后反转加好的链表结果即可。
[0,7,3]经过翻转后：
图片说明
[6,3]经过翻转后：

我们将翻转后的head1和head2按照加法模拟相加，模拟过程如下：
翻转后的7与3与进位0相加得值0，新的进位carry=1。

3与6与进位1相加得值0，新的进位carry=1

此时head2已经为NULL，但head1仍不为NULL，进位为1，我们依然把他们相加，得值0，新的进位carry=1
图片说明
最后还剩下一个进位carry=1，我们将其追加到ret得末尾，然后翻转就是最后结果了[1,0,0,0].

代码实现如下

ListNode* reverseList(ListNode* head) {
    if(!head) return NULL;
    ListNode* p = head->next;
    ListNode*temp;
    ListNode*q = head;
    while (p){
        temp = p->next;
        p->next = head;
        q->next = temp;
        head = p;
        p = temp;
    }
    return head;
}

ListNode *addInList(ListNode *head1, ListNode *head2) {
    ListNode *head = new ListNode(-1);
    head1 = reverseList(head1);
    head2 = reverseList(head2);
    ListNode *l1 = head1;
    ListNode *l2 = head2;
    ListNode *p = head;
    int carry = 0;
    while (l1 || l2 || carry) {
        int sum = carry;
        if (l1) {
            sum += l1->val;
            l1 = l1->next;
        }
        if (l2) {
            sum += l2->val;
            l2 = l2->next;
        }
        carry = sum / 10;
        int newsum = sum % 10;
        ListNode *tem = new ListNode(newsum);
        p->next = tem;
        p = p->next;
    }
    ListNode *ret = reverseList(head->next);
    return ret;
}

时间复杂度： $O(m+n)$ ，我们两个链表分别遍历了两次，最后结果遍历了一次。

空间复杂度：暂定说明，认为O(1)即可。

题解二（反转链表+递归求和）

在题解一的求和部分，我们是模拟加法的过程进行运算的，这部分可以转化为递归求和。

ListNode* reverseList(ListNode* head) {
    if(!head) return NULL;
    ListNode* p = head->next;
    ListNode*temp;
    ListNode*q = head;
    while (p){
        temp = p->next;
        p->next = head;
        q->next = temp;
        head = p;
        p = temp;
    }
    return head;
} 
ListNode *addTwoNumbersCore(ListNode *head1, ListNode *head2, int carry) {
    if (!head1 && !head2 && carry == 0) {
        // 当输入的节点均为null且无需处理进位时，结束
        return nullptr;
    }
    int val = carry + (head1 ? head1->val : 0) + (head2 ? head2->val : 0); // 计算当前的和
    auto ret = new ListNode(val % 10);
    ret->next = addTwoNumbersCore((head1 ? head1->next : nullptr), (head2 ? head2->next : nullptr), val / 10);
    return ret;
}
ListNode* addInList(ListNode* head1, ListNode* head2) {
   ListNode* l1 = reverseList(head1);
   ListNode* l2 = reverseList(head2);
   ListNode*ret = addTwoNumbersCore(l1, l2, 0);
   return reverseList(ret);
}

时间复杂度： $O(n+m)$ ,我们常数次遍历了两个链表

空间复杂度： $O(min(m,n))$ 在递归求和时，递归的深度取决于链表的长度。