🔥个人主页：Milestone-里程碑

❄️个人专栏: <<力扣hot100>> <<C++>><<Linux>>

       <<Git>><<MySQL>>

🌟心向往之行必能至

1. 题目描述

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

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

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

示例

输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807，逆序存储即为 7 -> 0 -> 8。

输入：l1 = [0], l2 = [0]
输出：[0]

输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出：[8,9,9,9,0,0,0,1]
解释：最高位产生进位，需要额外创建一个节点。

---

2. 解题思路

这道题的核心在于模拟我们日常进行竖式加法的过程，只不过操作对象是链表而不是数组或字符串。

关键点分析

1. 逆序存储的优势：由于数字是逆序存储的（个位在链表头），我们可以直接从链表头部开始遍历，依次对每一位进行相加，这与我们手算加法从低位到高位的顺序完全一致。
2. 进位处理 (carry)：这是本题的灵魂。每一位相加的结果可能大于等于 10，此时需要记录进位值（sum / 10），并在下一位的计算中加上这个进位。
3. 链表长度不一致：两个链表长度可能不同。当一个链表遍历结束后，另一个链表可能还有剩余节点，需要继续处理。
4. 最高位进位：当两个链表都遍历完成后，如果 carry 仍然不为 0（例如 5+5=10），则需要在结果链表的末尾再添加一个值为 1 的新节点。

算法步骤

1. 创建一个哑节点 (dummy node)。这是一个虚拟的头节点，它的 next 指针指向结果链表的真正头节点。使用哑节点可以避免处理头节点为空的特殊情况，简化代码逻辑。
2. 初始化一个指针 current 指向哑节点，用于构建结果链表。
3. 初始化进位变量 carry = 0。
4. 进入循环，循环条件是：l1 不为空 或 l2 不为空 或 carry 不为 0。
   • 取出 l1 当前节点的值（如果 l1 为空则取 0）。
   • 取出 l2 当前节点的值（如果 l2 为空则取 0）。
   • 计算总和：sum = val1 + val2 + carry。
   • 更新进位：carry = sum / 10。
   • 创建新节点，值为 sum % 10，并将其链接到 current->next。
   • 移动 current 指针到新节点。
   • 如果 l1 不为空，移动 l1 到下一个节点。
   • 如果 l2 不为空，移动 l2 到下一个节点。
5. 循环结束后，返回 dummy->next，即结果链表的头节点。

---

3. 代码实现 (C++)

你提供的代码注释部分其实就是正确的解法！下面我将其整理并加上详细注释：

cpp

编辑

1/**
2 * Definition for singly-linked list.
3 * struct ListNode {
4 *     int val;
5 *     ListNode *next;
6 *     ListNode() : val(0), next(nullptr) {}
7 *     ListNode(int x) : val(x), next(nullptr) {}
8 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
9 * };
10 */
11class Solution {
12public:
13    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
14        // 创建哑节点，简化头节点的处理
15        ListNode dummy(0);
16        ListNode* current = &dummy;
17        
18        int carry = 0; // 进位初始化为0
19        
20        // 循环条件：只要 l1 或 l2 还有节点，或者还有进位未处理
21        while (l1 != nullptr || l2 != nullptr || carry != 0) {
22            int sum = carry; // 当前位的和初始化为进位值
23            
24            // 如果 l1 还有节点，加上 l1 当前节点的值
25            if (l1 != nullptr) {
26                sum += l1->val;
27                l1 = l1->next; // 移动 l1 指针
28            }
29            
30            // 如果 l2 还有节点，加上 l2 当前节点的值
31            if (l2 != nullptr) {
32                sum += l2->val;
33                l2 = l2->next; // 移动 l2 指针
34            }
35            
36            // 计算新的进位和当前位的值
37            carry = sum / 10;       // 进位是 sum 除以 10 的商
38            int digit = sum % 10;   // 当前位的值是 sum 除以 10 的余数
39            
40            // 创建新节点并链接到结果链表
41            current->next = new ListNode(digit);
42            current = current->next; // 移动 current 指针
43        }
44        
45        // 返回哑节点的下一个节点，即结果链表的真正头节点
46        return dummy.next;
47    }
48};

---

4. 复杂度分析

• 时间复杂度: O(max⁡(m,n))O(max(m,n))

  • 其中 mm 和 nn 分别是链表 l1 和 l2 的长度。
  • 我们需要遍历两个链表，循环次数取决于较长的那个链表的长度。如果最后还有进位，会多执行一次循环，但这不影响整体的线性复杂度。

• 空间复杂度: O(max⁡(m,n))O(max(m,n))

  • 我们需要创建一个新的链表来存储结果。
  • 结果链表的长度最多为 max⁡(m,n)+1max(m,n)+1 （当最高位产生进位时）。
  • 如果不计算返回结果所占用的空间，只考虑额外使用的变量（如 carry, sum, 指针等），则空间复杂度为 O(1)O(1) 。但在算法分析中，通常将结果空间也计入，所以是 O(max⁡(m,n))O(max(m,n)) 。