【Hot 100 刷题计划】 LeetCode 2. 两数相加 | C++ 分支迭代法

LeetCode 2. 两数相加 题目描述题目级别中等给你两个非空的链表表示两个非负的整数。它们每位数字都是按照逆序的方式存储的并且每个节点只能存储一位数字。请你将两个数相加并以相同形式返回一个表示和的链表。你可以假设除了数字 0 之外这两个数都不会以 0 开头。示例 1:输入l1 [2,4,3], l2 [5,6,4]输出[7,0,8]解释342 465 807。 破题思路按位模拟与严谨的分支处理因为链表已经是逆序排列的个位在头高位在尾这刚好符合我们做“竖式加法”从低位向高位进位的习惯。我们可以维护一个进位/求和变量sum并在循环中严格区分三种物理情况l1和l2都没走完此时将两者的当前节点值相加并加上上一轮留下的进位sum。算出当前位sum % 10并接入结果链表同时更新进位sum / 10。只有l1没走完此时l2已经到头了只需要拿l1的值去和上一轮的进位sum相加计算当前位和新的进位。只有l2没走完同理只处理l2和进位sum的相加。极客细节虚拟头节点的内存管理在处理这种需要创建新链表的题目时很多时候我们会用ListNode* dummy new ListNode(0);来做虚拟头节点。但这在 C 中如果没有对应的delete是会导致内存泄漏的。这里的解法极其巧妙地使用了栈上分配ListNode res(0);然后再用指针ListNode* cur res;去进行后续的拼接。函数结束时res会被系统自动回收不仅运行速度更快而且做到了绝对的内存安全 C 代码实现classSolution{public:ListNode*addTwoNumbers(ListNode*l1,ListNode*l2){// 在栈上分配虚拟头节点安全高效杜绝内存泄漏ListNoderes(0);ListNode*curres;// sum 既用来记录当前的累加和也用来向下一位传递进位intsum0;while(l1||l2){// 情况 1两个链表都还有数字if(l1l2){suml1-vall2-val;cur-nextnewListNode(sum%10);// 取个位数接入新链表curcur-next;sum/10;// 取十位数作为进位保留到下一轮l1l1-next,l2l2-next;}// 情况 2l2 已经走完了只剩 l1elseif(l1){suml1-val;cur-nextnewListNode(sum%10);curcur-next;sum/10;l1l1-next;}// 情况 3l1 已经走完了只剩 l2elseif(l2){suml2-val;cur-nextnewListNode(sum%10);curcur-next;sum/10;l2l2-next;}}// 终极扫尾如果两个链表都走完了但最后还有进位没处理比如 9 9 18 的那个 1if(sum)cur-nextnewListNode(sum%10);// 返回虚拟头节点的下一个节点即真实的合并结果returnres.next;}};