力扣面试题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; // 返回结果链表的头节点
    }
};

五、总结

本题关键在于利用虚拟头节点消除头节点为空的特殊判断，结合迭代与进位处理实现链表的逐位相加。需注意循环条件需同时考虑链表遍历状态与进位，避免遗漏末尾进位的情况。此外，该解法无需反转链表或额外空间，是解决链表相加问题的经典思路。