链表(两数相加)(1)

一.题目2. 两数相加 - 力扣LeetCode二.思路讲解2.1 审题题目给出两个非空链表每个链表表示一个非负整数并且数字是逆序存储的即链表的头节点对应数字的最低位。例如链表2-4-3表示数字342。我们需要将这两个数相加并返回一个同样以逆序形式表示和的链表。题目保证除了数字 0 本身否则不会以 0 开头这确保了输入是合法的。2.2 虚拟头节点哨兵位在链表操作中经常需要处理头节点的特殊情况。例如当我们依次向结果链表中添加节点时第一个节点需要被设置为头节点后续节点则接在尾部。如果不用虚拟头节点就需要单独判断是否第一个节点这会使代码变得繁琐。因此我们引入一个虚拟头节点new_head它是一个哨兵节点不存储实际数据仅作为一个占位符。这样我们始终将新节点接在head初始指向虚拟头节点的后面然后移动head。最终返回new_head-next即可得到真正的结果链表头。这种方法避免了边界判断简化了代码逻辑。2.3 思路讲解本题的核心是模拟竖式加法从最低位链表头开始逐位相加并处理进位。具体步骤如下初始化两个指针cur1和cur2分别指向两个输入链表的头节点用于遍历。创建虚拟头节点new_head并让指针head也指向它head将始终指向当前结果链表的末尾。定义变量t用于存储当前位的和以及进位初始为 0。然后进入循环条件为cur1 ! nullptr || cur2 ! nullptr即只要有一个链表还有节点就继续处理。在循环中如果cur1非空则将其值加到t上并将cur1移向下一个节点。如果cur2非空同样将其值加到t上并将cur2移向下一个节点。然后当前位的和为t % 10我们创建一个新节点存入该值并将其接到head-next然后移动head到新节点。更新进位t t / 10用于下一轮计算。循环结束后可能还存在最后的进位即t不为 0此时需要再创建一个节点存放该进位值并接到链表末尾。最后返回new_head-next即结果链表的头节点。三.代码演示/** * 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) {} * }; */ class Solution { public: ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) { ListNode* cur1 l1; ListNode* cur2 l2; ListNode* new_head new ListNode; ListNode* head new_head; int t 0; while(cur1 ! nullptr || cur2 ! nullptr) { //判断l1是不是空节点 if(cur1 ! nullptr) { t cur1-val; cur1 cur1-next; } //判断l2是不是空节点 if(cur2 ! nullptr) { t cur2-val; cur2 cur2-next; } ListNode* node new ListNode(t % 10);//取t的个位数作为节点的值 t t / 10;//进位 head-next node;//让头节点连接该节点 head head -next;//让头节点往前 } if(t ! 0) { ListNode* node new ListNode(t % 10);//取t的个位数作为节点的值 head-next node;//让头节点连接该节点 } return new_head-next; } };四.代码讲解一、初始化遍历指针和虚拟头节点首先我们需要两个指针cur1和cur2分别指向输入链表l1和l2的头节点用于后续遍历。同时为了简化结果链表的构建我们创建一个虚拟头节点new_head它是一个哨兵节点不存储实际数据。再定义一个指针head也指向这个虚拟头节点head将始终指向当前结果链表的末尾方便我们添加新节点。此外定义一个整型变量t用于存储当前位的和以及进位初始化为 0。二、遍历两个链表进行逐位相加进入while循环条件为cur1 ! nullptr || cur2 ! nullptr即只要两个链表中还有未处理的节点就继续循环。这样能自动处理两个链表长度不一致的情况。在循环内部首先处理两个链表当前节点的值如果cur1不为空则将其值加到t上并将cur1移向下一个节点。如果cur2不为空同样将其值加到t上并将cur2移向下一个节点。此时t中存储的是当前位的和加上来自低位的进位。接着我们创建新节点其值为t % 10即当前位的个位数并将该节点连接到结果链表中将head-next指向这个新节点。然后将head移动到新节点即head head-next这样head始终指向结果链表的尾部。最后更新进位t t / 10为下一位的计算做准备。三、处理最后的进位当循环结束后可能还有一个进位未被处理即t不为 0。例如最高位相加后产生进位此时需要再创建一个新节点其值为t % 10实际上t此时就是进位值可能大于9吗实际上进位最多为1因为两个个位数相加最大99119所以t/10最大为1但为了通用性我们还是用取模。然后将这个节点连接到head-next。四、返回结果链表最后返回new_head-next即虚拟头节点的下一个节点也就是结果链表的真正头节点。五、关键细节虚拟头节点的作用避免了在插入第一个节点时需要特殊判断是否为空链表简化了代码逻辑。长度不一致的处理通过循环条件cur1 ! nullptr || cur2 ! nullptr以及在内部分别判断每个指针是否为空巧妙地处理了链表长度不等的情况。进位变量t的妙用t同时存储当前位的和以及进位每次计算后更新既简洁又高效。最后进位的处理循环结束后必须检查t是否非零否则会丢失最高位的进位。节点创建使用new ListNode(t % 10)动态创建新节点每个节点只存储一位数字。