题解 | 链表相加(二)

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
public:
    ListNode* reverse_list(ListNode* head)
    {
        ListNode* newhead = new ListNode(0);
        ListNode* cur = head;
        while(cur)
        {
            ListNode* tmp = cur->next;
            cur->next = newhead->next;
            newhead->next = cur;
            cur = tmp;
        }

        cur = newhead->next;
        delete newhead;
        return cur;
    }

    ListNode* addInList(ListNode* head1, ListNode* head2) 
    {
        head1 = reverse_list(head1);
        head2 = reverse_list(head2);

        int index = 0;
        ListNode* newhead = new ListNode(0);
        ListNode* cur = newhead;
        while(head1 || head2)
        {
            int val = index;
            if(head1) 
            {
                val += head1->val;
                head1 = head1->next;
            }
            if(head2)
            {
                val += head2->val;
                head2 = head2->next;
            }
            cur->next = new ListNode(val % 10);
            cur = cur->next;
            index = val / 10;
        }

        if(index) cur->next = new ListNode(index);
        
        cur = newhead->next;
        delete newhead;
        return reverse_list(cur);
    }
};

这道题只需要一个辅助函数, 也就是非常经典的反转链表的函数:

我的解法思路很清晰, 就是模拟

1 将两个链表进行反转, 从个位数开始加

2 添加进位标识符 index , 表示是否有无进位

3 最后判断进位标识符是否为空, 否则直接新建一个节点

4 最后最后, 一定要反转一下整个链表, 因为我这个是反转链表进行计算的

5 没有最后完成啦