力扣面试02.05题解：链表数字相加的完整实现指南

一、问题描述

给定两个非空链表，分别表示两个非负整数。数字以逆序存储，每个节点存储一位数字。将这两个数字相加并以相同形式的链表返回结果。

二、算法核心思想

本解决方案采用模拟竖式加法的方式：

1. 使用虚拟头节点简化链表操作

2. 同步遍历两个链表

3. 处理进位和不同长度的情况

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; // 当前位的和初始化为进位值
            
            // 处理l1链表当前位的值
            if (l1) {
                sum += l1->val;
                l1 = l1->next;
            }
            
            // 处理l2链表当前位的值
            if (l2) {
                sum += l2->val;
                l2 = l2->next;
            }
            
            carry = sum / 10; // 计算新的进位
            curr->next = new ListNode(sum % 10); // 创建新节点存储当前位结果
            curr = curr->next; // 移动当前节点指针
        }
        
        return dummy.next; // 返回结果链表的头节点
    }
};

四、算法分步解析

1. 初始化阶段：

• 创建虚拟头节点简化链表操作

• 初始化进位为0

2. 循环处理阶段：

• 同时遍历两个链表

• 处理不同长度链表的情况

• 计算当前位的和与进位

3. 结果构建阶段：

• 为每位结果创建新节点

• 维护链表连接关系

4. 结束处理：

• 检查最后是否有进位需要处理

• 返回结果链表的头节点

五、常见误区与调试技巧

1. 忘记处理最后进位的情况

2. 没有正确处理链表长度不等的情况

3. 链表连接关系处理错误

4. 进位计算错误

六、扩展思考

1. 如果数字是正序存储的该如何处理？

2. 如何优化空间复杂度？

3. 如何处理超大数相加的情况？