力扣面试题02.05链表相加：虚拟头节点+迭代解法的详细解析

15303105423

一、题目解读

力扣面试题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. 返回结果：虚拟头节点的下一个节点（即实际结果链表的头节点）。

四、代码与注释

1. class Solution {
   
2. public:
   
3.     ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
   
4.         ListNode dummy(0); // 虚拟头节点，简化边界处理
   
5.         ListNode* curr = &dummy; // 当前指针指向虚拟头节点
   
6.         int carry = 0; // 记录进位
   
7. 
   
8.         while (l1 || l2 || carry) { // 任一链表未遍历完或存在进位时继续
   
9.             int sum = carry; // 初始化当前位和
   
10.             if (l1) { // 若链表1有节点
    
11.                 sum += l1->val; // 累加节点值
    
12.                 l1 = l1->next; // 移动指针
    
13.             }
    
14.             if (l2) { // 若链表2有节点
    
15.                 sum += l2->val;
    
16.                 l2 = l2->next;
    
17.             }
    
18.             
    
19.             carry = sum / 10; // 更新进位
    
20.             curr->next = new ListNode(sum % 10); // 创建新节点存储余数
    
21.             curr = curr->next; // 指针后移
    
22.         }
    
23.         
    
24.         return dummy.next; // 返回结果链表的头节点
    
25.     }
    
26. };

复制代码

五、总结

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

来源：自学信奥