企业官网建设流程全解析

前言

本专栏文章为《LeetCode 热题 100》的刷题题解，相关内容如有侵权，立即删除。

一、题目

1、原题链接

2.两数相加

2、题目描述

二、个人思路整理

1、思路分析

核心思路：模拟竖式加法.
具体步骤：

1. 哨兵节点（Dummy Head）：使用一个虚拟头节点dummy，可以避免单独处理结果链表头节点的边界判断。
2. 维护进位变量carry：记录上一位相加后的进位值，初始为0。
3. 循环遍历：循环继续的条件为：l1不为空 或l2不为空 或carry != 0（防止最高位仍有进位遗漏，例如99 + 1 = 100 99 + 1 = 10099+1=100）。

• 提取当前位数值：若指针已指向空，则该位补0；
• 计算当前和：sum = val1 + val2 + carry；
• 新节点的值为：sum % 10；
• 更新进位：carry = sum / 10；
• 对应指针向后移动。

2、解题代码

/** * 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) {} * }; */classSolution{public:ListNode*addTwoNumbers(ListNode*l1,ListNode*l2){// 创建哨兵节点，简化头节点的处理逻辑ListNodedummy(0);// cur指针用于构建新链表，初始指向哨兵节点ListNode*cur=&dummy;// carry 记录当前位的进位值（0 或 1）intcarry=0;// 只要 l1、l2 还有未处理的节点，或者最高位还存在进位，就继续计算while(l1!=nullptr||l2!=nullptr||carry!=0){// 取当前节点的值；若指针为空则用 0 补齐intn1=(l1!=nullptr)?l1->val:0;intn2=(l2!=nullptr)?l2->val:0;// 计算当前位的总和（两数之和 + 上一轮的进位）intsum=n1+n2+carry;// 更新当前位产生的进位（传给下一轮计算）carry=sum/10;// 当前位只保留个位数值，并创建新节点挂在结果链表末尾cur->next=newListNode(sum%10);cur=cur->next;// 分别移动 l1 和 l2 的指针到下一位if(l1!=nullptr){l1=l1->next;}if(l2!=nullptr){l2=l2->next;}}// 哨兵节点的下一个节点即为最终结果链表的真正头节点returndummy.next;}};

复杂度分析

• 时间复杂度：O ( max ⁡ ( m , n ) ) O(\max(m, n))O(max(m,n))，其中m mm和n nn分别是两个链表的长度，只需遍历较长链表的长度次。
• 空间复杂度：O ( 1 ) O(1)O(1)，返回值占用的空间不计入额外空间复杂度。

三、知识风暴

模拟竖式加法是本题的核心思想：像小学竖式加法一样，从最低位（个位）开始逐位相加，同时维护进位carry，最终把每一位的结果串成新的链表。它把「两个链表逐位相加」这一过程拆解为「取位 → 求和 → 进位 → 建节点」四个固定步骤。

算法核心思想：

• 逐位相加：从两个链表的头节点（即最低位）开始，同步向后遍历，对应位相加。
• 进位传递：当前位之和sum = val1 + val2 + carry，新节点值为sum % 10，进位为sum / 10。
• 补零对齐：当某个链表先走完时，其后续位视为0，保证两个数位数不同也能正确相加。
• 最高位进位：循环条件包含carry != 0，避免遗漏最高位相加后产生的进位（如99 + 1 = 100 99 + 1 = 10099+1=100）。

常见对比：模拟竖式加法 vs 其他思路

使用要点：

• 哨兵节点：使用虚拟头节点dummy，避免单独处理结果链表头节点的边界判断，代码更简洁。
• 循环条件：while (l1 != nullptr || l2 != nullptr || carry != 0)，三者任一成立都要继续。
• 补零取值：int n1 = (l1 != nullptr) ? l1->val : 0;，指针为空时补0参与运算。
• 进位更新：carry = sum / 10;，由于每位最大为9 + 9 + 1 = 19 9 + 9 + 1 = 199+9+1=19，进位只可能是0或1。
• 指针移动：只有对应链表非空时才移动指针，避免空指针解引用。

算法变体与扩展：

1. 链表逆序存储：若数字按高位到低位存储，需先反转链表再相加（对应 LeetCode 445）。
2. 二进制链表相加：把十进制进位改为二进制进位，思路完全一致（对应 LeetCode 面试题 02.05）。
3. 字符串大数相加：把链表换成字符串，同样用「逐位相加 + 进位」处理超大整数。
4. 多链表相加：把两个链表扩展为多个链表，逐位累加所有链表当前位的值。

与其他算法的对比：

• 模拟竖式加法：O ( max ⁡ ( m , n ) ) O(\max(m, n))O(max(m,n))时间、O ( 1 ) O(1)O(1)空间，是本题最优解，也是面试中最常考察的解法。
• 先转整数再相加：思路简单，但链表长度超过整数范围时会溢出，仅适用于小数值场景。
• 递归相加：代码优雅，但递归深度等于链表长度，长链表下可能栈溢出，不具实用性。

相关 LeetCode 例题：

• 2. 两数相加（本题，模拟竖式加法）
• 445. 两数相加 II（链表逆序存储，需先反转再相加）
• 67. 二进制求和（字符串形式的二进制逐位相加）
• 415. 字符串相加（字符串形式的大数逐位相加）