C#求解LeetCode第2题：如何构造可在函数外生效的链表？

初始思路修正 #

你目前计划先将链表转整数相加再转回链表的思路存在边界缺陷：LeetCode本题测试用例会出现长度远超long类型上限的链表，直接转整数会发生溢出导致结果错误，更推荐直接逐位处理链表节点相加的方案。

疑问1：如何构造ListNode组成的结果链表 #

你可以用**哑节点（哨兵节点）**的技巧简化构建流程，不需要提前计算结果长度，边计算边追加节点即可：

• 先创建一个无业务意义的哑节点ListNode dummy = new ListNode();
• 再声明一个游标指针ListNode current = dummy;指向当前正在构建的最后一个节点
• 每算出一个新的数位值，就新建一个ListNode实例赋值给current.next，再把current向后移动一位
• 最终返回dummy.next就是结果链表的头节点

疑问2：函数内部创建的ListNode为什么外部可以访问 #

C#中ListNode是类，属于引用类型：

• 你在函数内部new的ListNode实例存储在堆内存中，不会随函数栈帧销毁而回收
• 函数返回的是堆上实例的引用地址，外部拿到这个地址就可以访问对应的对象
• 作用域限制的只是函数内部声明的变量名的生命周期，不会影响堆上存储的实际对象

疑问3：转整数为链表是否需要提前计算长度 #

不需要提前计算长度，你可以通过循环逐位取数构建：

// 仅做逻辑示例，此方法存在大数溢出问题，不推荐在本题使用
ListNode NumberToList(int sum) {
    ListNode dummy = new ListNode();
    ListNode current = dummy;
    if(sum == 0) return new ListNode(0); // 处理和为0的特殊情况
    while(sum > 0) {
        int digit = sum % 10;
        current.next = new ListNode(digit);
        current = current.next;
        sum = sum / 10;
    }
    return dummy.next;
}

本题标准逐位相加实现代码 #

public class Solution {
    public ListNode AddTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode();
        ListNode current = dummy;
        int carry = 0; // 存储进位值
        // 只要还有节点没处理或者还有未结算的进位就继续循环
        while(l1 != null || l2 != null || carry != 0) {
            int val1 = l1 == null ? 0 : l1.val;
            int val2 = l2 == null ? 0 : l2.val;
            int sum = val1 + val2 + carry;
            carry = sum / 10;
            current.next = new ListNode(sum % 10);
            current = current.next;
            if(l1 != null) l1 = l1.next;
            if(l2 != null) l2 = l2.next;
        }
        return dummy.next;
    }
}

内容的提问来源于stack exchange，提问作者Edward Suzuki