企业官网建设流程全解析

1. 题目

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

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

你可以假设除了数字 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]

2. 题解

2.1. 模拟

2.1.1. 核心思想

模拟人工竖式加法，从低位到高位逐位相加，保存进位，只要还有链表节点或者还有进位，就继续生成结果节点。

关键点拆解

1. 链表是逆序：链表头部天然对应数字最低位，直接从头遍历就是从个位开始相加，不需要反转链表。

2. 进位 carry：每一位总和 = l1 当前位 + l2 当前位 + 上一轮进位

   • 当前位值：sum % 10
   • 新进位：sum / 10

3. 长短链表兼容：某一条链表遍历完之后，该链表取值当作0，不用单独写一大段分支处理剩余链表。

4. 循环终止条件（非常关键）

   p1不为空 OR p2不为空 OR carry>0

   即使两条链表都走完，如果进位还有 1（例如 999+999 最后进位 1），必须再新建一个节点保存最高进位。

5. 虚拟头结点 (dummy 哑节点)

   • 消除 “是否是第一个节点” 的特殊判断，头节点、普通节点统一用tail->next = new ListNode()生成。
   • dummy 本身无意义，返回dummy->next作为真实结果头。

2.1.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){ListNode*dummy=newListNode();ListNode*tail=dummy;ListNode*p1=l1;ListNode*p2=l2;intcarry=0;// 进位// 只要p1不为空 或者 p2不为空 或者还有进位，就要继续建节点while(p1!=nullptr||p2!=nullptr||carry!=0){intv1=p1?p1->val:0;intv2=p2?p2->val:0;intsum=v1+v2+carry;carry=sum/10;intcurVal=sum%10;// 堆上新建节点，不能栈对象！tail->next=newListNode(curVal);tail=tail->next;if(p1)p1=p1->next;if(p2)p2=p2->next;}// dummy是虚拟头，真正结果从dummy->next开始returndummy->next;}};

2.1.3. 复杂度

时间复杂度：O ( max ⁡ ( n , m ) ) O(\max(n,m))O(max(n,m))，n、m 是两个链表长度，最多遍历较长链表 + 一次进位。
空间复杂度：O ( max ⁡ ( n , m ) ) O(\max(n,m))O(max(n,m))，新建结果链表；不算输出链表空间则为( O ( 1 ) (O(1)(O(1)。

3.2. 两数相加 - 力扣（LeetCode）