文章目录前言一、题目1、原题链接2、题目描述二、个人思路整理1、思路分析2、解题代码三、知识风暴前言本专栏文章为《LeetCode 热题 100》的刷题题解相关内容如有侵权立即删除。一、题目1、原题链接2.两数相加2、题目描述二、个人思路整理1、思路分析核心思路模拟竖式加法.具体步骤哨兵节点Dummy Head使用一个虚拟头节点dummy可以避免单独处理结果链表头节点的边界判断。维护进位变量carry记录上一位相加后的进位值初始为0。循环遍历循环继续的条件为l1不为空 或l2不为空 或carry ! 0防止最高位仍有进位遗漏例如99 1 100 99 1 100991100。提取当前位数值若指针已指向空则该位补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*curdummy;// carry 记录当前位的进位值0 或 1intcarry0;// 只要 l1、l2 还有未处理的节点或者最高位还存在进位就继续计算while(l1!nullptr||l2!nullptr||carry!0){// 取当前节点的值若指针为空则用 0 补齐intn1(l1!nullptr)?l1-val:0;intn2(l2!nullptr)?l2-val:0;// 计算当前位的总和两数之和 上一轮的进位intsumn1n2carry;// 更新当前位产生的进位传给下一轮计算carrysum/10;// 当前位只保留个位数值并创建新节点挂在结果链表末尾cur-nextnewListNode(sum%10);curcur-next;// 分别移动 l1 和 l2 的指针到下一位if(l1!nullptr){l1l1-next;}if(l2!nullptr){l2l2-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 100991100。常见对比模拟竖式加法 vs 其他思路方法核心思路时间复杂度空间复杂度适用场景模拟竖式加法逐位相加 进位传递边遍历边建新链表O ( max ⁡ ( m , n ) ) O(\max(m, n))O(max(m,n))O ( 1 ) O(1)O(1)不计返回值本题标准解法直观高效先转整数再相加把两个链表还原为整数相加后再拆回链表O ( m n ) O(m n)O(mn)O ( 1 ) O(1)O(1)仅适用于数值较小、无溢出风险的场景递归相加递归处理每一位回溯时处理进位O ( max ⁡ ( m , n ) ) O(\max(m, n))O(max(m,n))O ( max ⁡ ( m , n ) ) O(\max(m, n))O(max(m,n))递归栈链表较长时可能栈溢出不推荐使用要点哨兵节点使用虚拟头节点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 1999119进位只可能是0或1。指针移动只有对应链表非空时才移动指针避免空指针解引用。算法变体与扩展链表逆序存储若数字按高位到低位存储需先反转链表再相加对应 LeetCode 445。二进制链表相加把十进制进位改为二进制进位思路完全一致对应 LeetCode 面试题 02.05。字符串大数相加把链表换成字符串同样用「逐位相加 进位」处理超大整数。多链表相加把两个链表扩展为多个链表逐位累加所有链表当前位的值。与其他算法的对比模拟竖式加法O ( max ⁡ ( m , n ) ) O(\max(m, n))O(max(m,n))时间、O ( 1 ) O(1)O(1)空间是本题最优解也是面试中最常考察的解法。先转整数再相加思路简单但链表长度超过整数范围时会溢出仅适用于小数值场景。递归相加代码优雅但递归深度等于链表长度长链表下可能栈溢出不具实用性。相关 LeetCode 例题2. 两数相加本题模拟竖式加法445. 两数相加 II链表逆序存储需先反转再相加67. 二进制求和字符串形式的二进制逐位相加415. 字符串相加字符串形式的大数逐位相加