题目描述给你两个非空的链表表示两个非负的整数。它们每位数字都是按照逆序的方式存储的并且每个节点只能存储一位数字。请你将两个数相加并以相同形式返回一个表示和的链表。你可以假设除了数字 0 之外这两个数都不会以 0 开头。示例 1输入l1 [2,4,3], l2 [5,6,4]输出[7,0,8]解释342 465 807.示例 2输入l1 [0], l2 [0]输出[0]示例 3输入l1 [9,9,9,9,9,9,9], l2 [9,9,9,9]输出[8,9,9,9,0,0,0,1]解题思路方法一模拟竖式加法关键观察逆序存储的好处是从链表头开始遍历正好是从个位开始相加符合竖式加法的顺序。342 465 ----- 807 个位: 257, 进位0 十位: 4610, 写0进1 百位: 3418, 进位0处理步骤同时遍历两个链表逐位相加处理进位sum val1 val2 carry处理剩余如果某个链表还有剩余继续加如果最后还有进位再加一个节点具体过程示例l1 2 - 4 - 3,l2 5 - 6 - 4dummy - null curr dummy carry 0 第1步: 2 5 0 7, carry 0 dummy - 7 l1 4, l2 6 第2步: 4 6 0 10, 写 0, carry 1 dummy - 7 - 0 l1 3, l2 4 第3步: 3 4 1 8, carry 0 dummy - 7 - 0 - 8 l1 null, l2 null 第4步: 两个链表都为空, carry 0, 结束 返回 dummy-next 7 - 0 - 8 ✅代码实现class Solution { public: ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) { ListNode *dummy new ListNode(0); // 虚拟头结点 ListNode *curr dummy; int carry 0; // 进位 while (l1 ! nullptr || l2 ! nullptr || carry ! 0) { // 取当前位的值如果链表为空取0 int val1 (l1 ! nullptr) ? l1-val : 0; int val2 (l2 ! nullptr) ? l2-val : 0; // 计算当前位的和 int sum val1 val2 carry; carry sum / 10; // 进位 int digit sum % 10; // 当前位的数字 // 新建节点 curr-next new ListNode(digit); curr curr-next; // 移动指针 if (l1 ! nullptr) l1 l1-next; if (l2 ! nullptr) l2 l2-next; } return dummy-next; } };复杂度分析维度复杂度说明时间复杂度O(max(n, m))n 和 m 分别是两个链表的长度空间复杂度O(max(n, m))结果链表的长度不算输出的话是 O(1)关键细节1. 为什么循环条件是l1 || l2 || carrywhile (l1 ! nullptr || l2 ! nullptr || carry ! 0)三种情况都要继续l1还有节点l2还有节点还有进位比如5 5 10最后还要加一个节点例子l1 5,l2 5第1步5510写0进1两个链表都空了但carry 1还需要再加一个节点第2步0011写1carry0结果0 - 1表示10✅2. 为什么用虚拟头结点ListNode *dummy new ListNode(0); ListNode *curr dummy;避免单独处理第一个节点的情况返回dummy-next即可3. 取值的技巧int val1 (l1 ! nullptr) ? l1-val : 0;如果l1已经为空就取0这样两个链表长度不同也能正确处理。4. 进位的计算carry sum / 10; // 进位0 或 1 int digit sum % 10; // 当前位的数字因为每位最多 99119所以carry最多是1。方法二递归class Solution { public: ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) { return add(l1, l2, 0); } ListNode* add(ListNode* l1, ListNode* l2, int carry) { if (l1 nullptr l2 nullptr carry 0) return nullptr; int val1 (l1 ! nullptr) ? l1-val : 0; int val2 (l2 ! nullptr) ? l2-val : 0; int sum val1 val2 carry; ListNode *node new ListNode(sum % 10); node-next add( (l1 ! nullptr) ? l1-next : nullptr, (l2 ! nullptr) ? l2-next : nullptr, sum / 10 ); return node; } };复杂度时间 O(max(n, m))空间 O(max(n, m))递归栈两种方法对比方法时间复杂度空间复杂度推荐度迭代 虚拟头结点O(max(n, m))O(max(n, m))⭐⭐⭐⭐⭐递归O(max(n, m))O(max(n, m))⭐⭐⭐⭐总结要点说明核心思想模拟竖式加法逐位相加处理进位关键变量carry进位、sum当前位和循环条件l1 || l2 || carry三者有一个就继续时间复杂度O(max(n, m))空间复杂度O(max(n, m))