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

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head1 ListNode类 
     * @param head2 ListNode类 
     * @return ListNode类
     */
    ListNode* addInList(ListNode* head1, ListNode* head2) {
        // write code here
        head1 = reverseList(head1);
        head2 = reverseList(head2);
        ListNode* headd = new ListNode(-1);
        ListNode* anshead = headd;
        int tmp = 0;
        while (head1!=nullptr || head2!=nullptr) {
            int val = tmp;
            if (head1!=nullptr) {
                val += head1->val;
                head1 = head1->next;
            }
            if (head2!=nullptr) {
                val += head2->val;
                head2 = head2->next;
            }
            tmp = val/10;
            anshead->next = new ListNode(val%10);
            anshead = anshead->next;
        }
        if (tmp>0) {
            anshead->next = new ListNode(tmp);
        }
        return reverseList(headd->next);
    }

    ListNode* reverseList(ListNode* head) {
        // write code here
        ListNode* newhead=nullptr;
        while (head!=nullptr) {
            ListNode* tmp = head->next;
            head->next = newhead;
            newhead = head;
            head = tmp;
        }
        return newhead;
    }
};

解题思路：

1.反转链表

2.反转后，使用val计数器，对两个数的各自节点数字累加，并求进位

3.val%10作为节点数字，将此节点新建，并作为当前节点的下一个指向的节点，val/10作为进位。

4.反转答案链表，返回

小注意：AB两个变量都指向同一个节点，另A变量移动节点位置时，不会影响B变量的节点移动。B变量添加后置节点时，A也会在相同节点随之添加。

因此，对B变量做新节点建立，返回实时保存每一个节点的变量A