链表正序存储两数相加递归解法空指针异常排查与思路验证

问题描述 #

给定两个非空链表，分别表示两个非负整数，数字按正序存储（链表头为最高位，尾为最低位），每个节点存一位数字。将两数相加，结果以链表形式返回，除数字0外，两数无前置零。

示例：

输入: l1 = [2,4,3], l2 = [5,6,4]
输出: [8,0,7]
解释: 243 + 564 = 807

链表节点定义如下：

// Definition for singly-linked list.
public class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

尝试的递归实现代码 #

import java.util.HashMap;

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode head = new ListNode(0);
        head.val = generateSumList(l1.next, l2.next, head.next);
        return head;
    }


    public int generateSumList(ListNode l1, ListNode l2, ListNode res) {
        
        int rest, sum;

        if (l1.next == null && l2.next != null) {
            return generateSumList(l1, l2.next, res.next);
        }

        if (l1.next != null && l1.next == null) {
            return generateSumList(l1.next, l2, res.next);
        }

        if (l1.next == null && l2.next == null) {
            sum = l1.val + l2.val;
            if (sum > 9) {
                ListNode n = new ListNode(sum % 10, null);
                res = n;
                return 1;
            }
            else {
                ListNode n = new ListNode(sum, null);
                res = n;
                return 0;
            }
        }

        rest = generateSumList(l1.next, l2.next, res.next);
        sum = l1.val + l2.val + rest;
        if (sum > 9) {
            res.val = sum % 10;
            return 1;
        }
        else {
            res.val = sum;
            return 0;
        }
    }
}

遇到的空指针异常 #

java.lang.NullPointerException: Cannot read field "next" because "<parameter1>" is null
  at line 27, Solution.generateSumList
  at line 17, Solution.addTwoNumbers
  at line 54, __DriverSolution__.__helper__
  at line 87, __Driver__.main

问题分析 #

1. 空指针异常的直接原因 #

• 空参数的属性访问：在addTwoNumbers中调用generateSumList(l1.next, l2.next, head.next)时，若l1或l2是单节点链表，l1.next或l2.next会是null，传入generateSumList后，方法第一行判断l1.next == null时，会尝试访问null对象的next属性，触发NPE。
• 逻辑判断矛盾：第二个条件if (l1.next != null && l1.next == null)存在逻辑错误，实际应为判断l2.next == null，但即使修正，当l1为null时，访问l1.next仍会触发NPE。
• 未初始化的结果节点：head.next初始为null，传入generateSumList后，递归调用res.next时会访问null对象的next属性，同样触发NPE。

2. 解题思路的核心问题 #

• 递归起点错误：题目中链表是正序存储（头为最高位），相加需从最低位（链表尾）开始，但代码直接跳过了头节点（传入l1.next和l2.next），完全遗漏了最高位的计算。
• 值传递无法构建结果链表：Java是值传递，generateSumList中对res的赋值（如res = n）不会影响外部的head.next，无法正确拼接结果链表。
• 未处理链表长度不一致：当两个链表长度不同时，代码仅简单递归跳过，未对短链表补0处理，导致计算错误。
• 未处理最终进位：若最后一次相加仍有进位（如999+999=1998），代码无法新增节点存储进位值。

修正后的递归实现思路与代码 #

正确的递归逻辑应从链表尾（最低位）开始计算，先递归到末尾，再从后往前构建结果链表，同时处理长度不一致和最终进位：

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        // 补全短链表的前置0，保证两链表长度一致
        int len1 = getLength(l1);
        int len2 = getLength(l2);
        if (len1 > len2) {
            l2 = padZero(l2, len1 - len2);
        } else {
            l1 = padZero(l1, len2 - len1);
        }
        
        int[] carry = new int[1]; // 用数组保存进位，利用引用类型传递状态
        ListNode result = addRecursive(l1, l2, carry);
        
        // 处理最终剩余的进位
        if (carry[0] == 1) {
            return new ListNode(1, result);
        }
        return result;
    }

    // 计算链表长度
    private int getLength(ListNode node) {
        int len = 0;
        while (node != null) {
            len++;
            node = node.next;
        }
        return len;
    }

    // 为短链表补前置0
    private ListNode padZero(ListNode node, int count) {
        ListNode dummy = new ListNode(0);
        ListNode curr = dummy;
        for (int i = 0; i < count; i++) {
            curr.next = new ListNode(0);
            curr = curr.next;
        }
        curr.next = node;
        return dummy.next;
    }

    // 递归计算，从尾到头构建结果链表
    private ListNode addRecursive(ListNode l1, ListNode l2, int[] carry) {
        if (l1 == null && l2 == null) {
            carry[0] = 0;
            return null;
        }
        // 先递归处理下一位（低位）
        ListNode nextNode = addRecursive(l1.next, l2.next, carry);
        // 计算当前位的和与进位
        int sum = l1.val + l2.val + carry[0];
        carry[0] = sum / 10;
        // 创建当前节点，拼接已构建的低位链表
        ListNode currNode = new ListNode(sum % 10);
        currNode.next = nextNode;
        return currNode;
    }
}

内容的提问来源于stack exchange，提问作者Marco Sperindeo