【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*cur=&res;// sum 既用来记录当前的累加和，也用来向下一位传递进位intsum=0;while(l1||l2){// 情况 1：两个链表都还有数字if(l1&&l2){sum+=l1->val+l2->val;cur->next=newListNode(sum%10);// 取个位数接入新链表cur=cur->next;sum/=10;// 取十位数作为进位保留到下一轮l1=l1->next,l2=l2->next;}// 情况 2：l2 已经走完了，只剩 l1elseif(l1){sum+=l1->val;cur->next=newListNode(sum%10);cur=cur->next;sum/=10;l1=l1->next;}// 情况 3：l1 已经走完了，只剩 l2elseif(l2){sum+=l2->val;cur->next=newListNode(sum%10);cur=cur->next;sum/=10;l2=l2->next;}}// 终极扫尾：如果两个链表都走完了，但最后还有进位没处理（比如 9 + 9 = 18 的那个 1）if(sum)cur->next=newListNode(sum%10);// 返回虚拟头节点的下一个节点，即真实的合并结果returnres.next;}};