跳到主要内容

两数相加

题目描述​

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

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

示例​

输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.

提示：

  • 每个链表中的节点数在范围 [1, 100] 内
  • 0 <= Node.val <= 9
  • 题目数据保证列表表示的数字不含前导零

解题思路​

模拟手工加法

从两个链表表示的数字的最低位（链表头）开始逐位相加，同时处理进位。

算法优化了空间使用，通过复用较长的链表来存储结果，而不是创建全新的节点。

时间复杂度：O(max(m, n)) 空间复杂度：O(1)

C++ 解法​

#include <algorithm>

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) {}
};

static int length(ListNode* p)
{
    int n = 0;
    while (p) {
        ++n;
        p = p->next;
    }
    return n;
}

class Solution {
public:
    // 原地复用较长链表，无需频繁分配新节点
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2)
    {
        // 让 l1 始终是较长的链表，结果写回 l1
        if (length(l1) < length(l2)) std::swap(l1, l2);
        ListNode* head = l1;

        int carry = 0;
        ListNode *p1 = l1, *p2 = l2, *prev = nullptr;

        while (p1) {
            int y = p2 ? p2->val : 0;
            int sum = p1->val + y + carry;
            p1->val = sum % 10; // 存储个位的数字
            carry = sum / 10;   // 存储进位

            prev = p1;          // 存储当前节点后移动 p1 和 p2
            p1 = p1->next;
            if (p2) p2 = p2->next;
        }

        // 如果还有进位，就在末尾补一个新节点
        if (carry) {
            prev->next = new ListNode(carry);
        }
        return head;
    }
};

LeetCode链接： 2. 两数相加