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. 核心思想模拟人工竖式加法从低位到高位逐位相加保存进位只要还有链表节点或者还有进位就继续生成结果节点。关键点拆解链表是逆序链表头部天然对应数字最低位直接从头遍历就是从个位开始相加不需要反转链表。进位 carry每一位总和 l1 当前位 l2 当前位 上一轮进位当前位值sum % 10新进位sum / 10长短链表兼容某一条链表遍历完之后该链表取值当作0不用单独写一大段分支处理剩余链表。循环终止条件非常关键p1不为空 OR p2不为空 OR carry0即使两条链表都走完如果进位还有 1例如 999999 最后进位 1必须再新建一个节点保存最高进位。虚拟头结点 (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*dummynewListNode();ListNode*taildummy;ListNode*p1l1;ListNode*p2l2;intcarry0;// 进位// 只要p1不为空 或者 p2不为空 或者还有进位就要继续建节点while(p1!nullptr||p2!nullptr||carry!0){intv1p1?p1-val:0;intv2p2?p2-val:0;intsumv1v2carry;carrysum/10;intcurValsum%10;// 堆上新建节点不能栈对象tail-nextnewListNode(curVal);tailtail-next;if(p1)p1p1-next;if(p2)p2p2-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