Leetcode 445. 两数相加 II

原题链接: 445. 两数相加 II - 力扣（LeetCode）

tag: 链表.

在阅读本文前, 请先阅读如下两篇题解.

Leetcode 206. 反转链表 - 掘金 (juejin.cn)

Leetcode 2. 两数相加 - 掘金 (juejin.cn)

一. 题目

给你两个 非空 链表来代表两个非负整数. 数字最高位位于链表开始位置. 它们的每个节点只存储一位数字. 将这两数相加会返回一个新的链表.

你可以假设除了数字 0 之外, 这两个数字都不会以零开头.

二. 题解

先将给定的两个链表 l1 , l2 反转.

反转链表 l1 .

l1 = reverseList(l1);

反转链表 l2 .

l2 = reverseList(l2);

经过与 Leetcode 2. 两数相加 一样的操作之后.

反转新链表.

head = reverseList(head);

返回新链表的头节点.

return head;

三. 复杂度分析

时间复杂度: O(max(M, N)), 其中 M 和 N 分别表示两个链表 l1 和 l2 的长度.

空间复杂度: O(1).

四. 代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* prev = nullptr, * curr = head;    // 定义前指针 prev, 中指针 curr
        while (curr != nullptr) {
            ListNode* temp = curr->next;    // 保存 curr 的后继节点
            curr->next = prev;    // 进行反转操作
            prev = curr;    // 更新 prev 指针
            curr = temp;    // 更新 curr 指针
        }
        return prev;    // 返回新的头节点
    }

    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        l1 = reverseList(l1);    // 反转链表 l1
        l2 = reverseList(l2);    // 反转链表 l2
        ListNode* dummy = new ListNode(), * tail = dummy;    // 创造一个虚拟头节点 dummy 用来尾插新节点
        int carry = 0;    // carry 表示当前位的值
        while (l1 || l2 || carry) {    // 从低位到高位遍历两个非负整数
            if (l1) {
                carry += l1->val;
                l1 = l1->next;    // 更新 l1 指针
            }
            if (l2) {
                carry += l2->val;
                l2 = l2->next;    // 更新 l2 指针
            }
            tail->next = new ListNode(carry % 10);    // 将新节点尾插到 dummy 后面
            tail = tail->next;    // 更新 tail 指针
            carry /= 10;    // carry 进位
        }
        ListNode* head = dummy->next;     
        delete dummy;
        head = reverseList(head);    // 反转新链表
        return head;    // 返回新链表的头节点   
    }
};