题目

题目链接

链表相加(二)_牛客题霸_牛客网

题目描述

代码实现

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head1 ListNode类 
     * @param head2 ListNode类 
     * @return ListNode类
     */
    ListNode* addInList(ListNode* head1, ListNode* head2) {
        // write code here
        if(head1 == nullptr) return head2;
        if(head2 == nullptr) return head1;
        ListNode *Head1 = reverseList(head1), *Head2 = reverseList(head2);
        ListNode *phead = new ListNode(-1), *cur = phead;//构造哨兵位节点管理后边的新链表
        int carry = 0;//进位
        while(Head1 || Head2 || carry){
            int val1 = Head1 == nullptr ? 0 : Head1->val;
            int val2 = Head2 == nullptr ? 0 : Head2->val;

            int tmp = val1 + val2 + carry;
            carry = tmp / 10;
            tmp %= 10;

            ListNode* newNode = new ListNode(tmp);
            cur->next = newNode;
            cur = cur->next;
            if(Head1) Head1 = Head1->next;
            if(Head2) Head2 = Head2->next;
        }
        return reverseList(phead->next);
    }
    ListNode* reverseList(ListNode* head){//反转链表
        if(head->next == nullptr || head == nullptr) return head;
        ListNode* newHead = reverseList(head->next);
        head->next->next = head;
        head->next = nullptr;
        return newHead;
    }
};

思路分析

1、首先，对于单链表，我们往往从头节点使用更加方便。这里对两个链表进行相加，最先对链表尾部的数字进行相加。对此，我们首先对两个链表进行反转。对于链表的反转可以参考我的这篇博文

反转链表+牛客-CSDN博客

2、其次，我们就是对头节点进行相加。对于加法我们需要考虑进位。其次考虑其中的链表访问完之后，应该取0的情况。

3、然后，我们的结果相对于要求是相反的。还需要再进行反转链表即可。

4、最后，我们靠需要考虑些特殊情况，当其中一个链表为空的时候，我们可以将另外的一个链表直接返回即可。