力扣第2题：三步掌握递归解法与进位传递技巧

给定两个非空链表，每个链表代表一个非负整数。数字按照逆序存储（如整数 342 存储为 2→4→3），要求将这两个数相加并以相同形式的链表返回结果。例如输入 2→4→3 和 5→6→4，它们的和是 807，输出应为 7→0→8。问题本质是实现按位相加，并处理进位和链表长度不一致的情况。

‌递归解法思路与过程‌：

1‌.递归终止条件‌：当两个链表均为空且无进位时结束递归。

‌2.补齐短链表‌：若其中一个链表已走到末尾，则创建一个值为 0 的节点，保证后续递归中位数对齐。

‌3.计算当前值和进位‌：将当前位的值相加并加上进位，取模得到当前节点值，整除得到新的进位。

4‌.递归连接节点‌：新建节点保存当前位的值，并将其作为当前节点的后继，继续递归处理下一位。

代码：

class Solution {
public:
    void add(ListNode* l1, ListNode* l2, int a, ListNode* head) {
        // 终止条件：两链表为空且进位为0
        if (l1 || l2 || a != 0) {
            // 若当前链表指针为空，创建值为0的节点补齐
            if (!l1) {
                ListNode* tmp = new ListNode(0);
                l1 = tmp;
            }
            if (!l2) {
                ListNode* tmp = new ListNode(0);
                l2 = tmp;
            }
            // 新建节点存储当前位的计算结果
            ListNode* tmp = new ListNode;
            int b = l1->val + l2->val + a;  // 当前位的和（包括进位）
            tmp->val = b % 10;               // 当前位的值
            a = b / 10;                      // 新的进位
            head->next = tmp;                // 将当前节点连接到结果链表
            // 递归处理下一位，传入下一节点和进位
            add(l1->next, l2->next, a, tmp);
        }
    }

    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* head = new ListNode;      // 创建哑节点作为结果链表的头部
        add(l1, l2, 0, head);               // 从初始进位0开始递归
        return head->next;                  // 返回哑节点的后继，即真正的结果链表
    }
};