力扣面试题02.05链表相加:虚拟头节点+迭代解法的详细解析
一、题目解读
力扣面试题02.05要求将两个链表表示的整数相加,每个节点存储一位数字(逆序),结果同样以链表形式返回。例如,链表1为7→2→4,链表2为5→6→3,相加结果应为2→9→8→7。题目难点在于处理链表长度不一致、末尾进位以及逆序数字的相加逻辑。
二、解题思路
1. 创建虚拟头节点(dummy)避免处理头节点为空的边界条件;
2. 通过迭代同时遍历两个链表,逐位相加并处理进位;
3. 利用carry变量记录当前位进位,每次迭代更新节点值(sum % 10)与进位(sum / 10);
4. 当任一链表未遍历完或存在进位时,继续迭代,确保处理末尾进位(如5+7=12需额外节点)。
该解法简洁高效,无需额外数据结构,时间复杂度O(max(m,n)),空间复杂度O(1)。
三、解题步骤
1. 初始化:创建虚拟头节点dummy,当前指针curr指向dummy,进位carry初始化为0;
2. 迭代相加:
当l1或l2存在节点或carry>0时循环:
计算当前位和sum(包含进位+节点值);
更新进位carry = sum / 10;
创建新节点存储sum % 10,并链接到curr->next;
移动指针curr至新节点。
3. 处理末尾:循环结束后,若carry>0(如末尾进位),需额外添加节点;
4. 返回结果:虚拟头节点的下一个节点(即实际结果链表的头节点)。
四、代码与注释
class Solution { public: ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) { ListNode dummy(0); // 虚拟头节点,简化边界处理 ListNode* curr = &dummy; // 当前指针指向虚拟头节点 int carry = 0; // 记录进位 while (l1 || l2 || carry) { // 任一链表未遍历完或存在进位时继续 int sum = carry; // 初始化当前位和 if (l1) { // 若链表1有节点 sum += l1->val; // 累加节点值 l1 = l1->next; // 移动指针 } if (l2) { // 若链表2有节点 sum += l2->val; l2 = l2->next; } carry = sum / 10; // 更新进位 curr->next = new ListNode(sum % 10); // 创建新节点存储余数 curr = curr->next; // 指针后移 } return dummy.next; // 返回结果链表的头节点 } };
五、总结
本题关键在于利用虚拟头节点消除头节点为空的特殊判断,结合迭代与进位处理实现链表的逐位相加。需注意循环条件需同时考虑链表遍历状态与进位,避免遗漏末尾进位的情况。此外,该解法无需反转链表或额外空间,是解决链表相加问题的经典思路。
原创内容 转载请注明出处