2. 两数相加

✨核心逻辑

本题采用 模拟数学加法（竖式运算） 的策略：

虚拟头节点：为了简化链表头节点的操作，我们创建一个虚拟头节点 dummy（代码中的 l3），它的 next 指针最终指向结果链表的第一个有效节点。
逐位相加：由于链表已经按照逆序存储数字（个位在头节点），我们可以直接从链表头开始同步遍历，将两个链表当前节点的值以及前一位的进位 carry 相加。
处理链表长度不一：如果一个链表长，一个链表短，当短链表走完时，其对应位置的值视为 0 进行运算即可。
处理最终进位：即使两个链表都遍历结束，如果最终进位 carry 仍然大于 0，必须额外创建一个新的节点存放这个进位。
指针移动：在创建当前位节点后，需要移动工作指针 cur（即代码中的 l4）指向新节点，并将 l1 和 l2 向后移动。
(解惑)：代码中的 l3 是 new 出来的一个对象，保存的是该对象在内存中的地址（引用）。l4 同样指向这个地址。后续 l4 = l4.next 只改变 l4 的指向，而 l3 的引用始终不变，因此最后返回 l3.next 就能正确拿到结果链表的头。

🔥代码实现（含详细变量注释）

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        // l3：虚拟头节点（Dummy Head），不存储有效数据，它的 next 指向结果链表的第一个节点
        ListNode l3 = new ListNode(0);
        // l4：工作指针，用于遍历并串联新生成的节点，初始指向 l3
        ListNode l4 = l3;
        // carry：记录两数相加产生的进位，初始化为 0
        int carry = 0;
        
        // 只要 l1 有值，或者 l2 有值，或者还有进位没处理完，就继续循环
        while (l1 != null || l2 != null || carry != 0) {
            // n1：当前 l1 指向节点的值，如果 l1 已经遍历完为 null，则取 0
            int n1 = l1 == null ? 0 : l1.val;
            // n2：当前 l2 指向节点的值，如果 l2 已经遍历完为 null，则取 0
            int n2 = l2 == null ? 0 : l2.val;
            
            // num：当前位的总和（两个数字之和 + 前一位的进位）
            int num = n1 + n2 + carry;
            
            // 更新进位：总和除以 10 取整
            carry = num / 10;
            // x：当前节点应该保存的数值（总和除以 10 取余，即个位数）
            int x = num % 10;
            
            // 根据当前位的数值 x 创建一个新节点
            ListNode l = new ListNode(x);
            // 将新节点串联到结果链表的尾部
            l4.next = l;
            // 工作指针 l4 向后移动，指向新加入的这个节点
            l4 = l;
            
            // 如果 l1 没走完，将 l1 指针向后移动一位
            if (l1 != null) l1 = l1.next;
            // 如果 l2 没走完，将 l2 指针向后移动一位
            if (l2 != null) l2 = l2.next;
        }
        
        // 返回虚拟头节点的下一个节点，即真正的结果链表的头节点
        return l3.next;
    }
}

⏱️复杂度分析
- 时间复杂度：O(max(M, N))，其中 M 和 N 分别代表两个链表的长度。我们需要遍历两个链表中最长的那一个，且最多额外处理一次进位。
- 空间复杂度：O(max(M, N))。我们需要创建一个新的结果链表来存储相加后的结果，新链表的最大长度为 max(M, N) + 1（当存在最终进位时）。