Java递归实现链表截断功能测试不通过求bug排查及修正方案

问题根因 #

代码的核心错误是递归传参时使用了后置自减运算符numNodes--：后置自减的逻辑是先将numNodes的原始值传递给下一层递归，再对当前层的变量做减1操作，导致所有递归层拿到的numNodes都是初始输入值，没有逐层递减，截断判断逻辑完全失效。同时原代码缺少numNodes <= 0的提前终止判断，会产生无效递归。

修正后的递归实现代码 #

public static ListNode truncate(ListNode head, int numNodes) {
    // 递归终止条件：链表遍历完毕 或 需要保留的节点数为0，直接返回null
    if (head == null || numNodes <= 0) {
        return null;
    }
    // 下一层递归传递剩余需要保留的节点数：当前节点已占用1个名额，剩余数量减1
    head.next = truncate(head.next, numNodes - 1);
    // 返回当前节点（已拼接好截断后的后续链表）
    return head;
}

逻辑验证（对应失败用例） #

针对长度为4的链表[10,11,12,13]、numNodes=3的场景，执行流程如下：

1. 第一层处理节点10，剩余保留数3>0，递归处理节点11，传入保留数2
2. 第二层处理节点11，剩余保留数2>0，递归处理节点12，传入保留数1
3. 第三层处理节点12，剩余保留数1>0，递归处理节点13，传入保留数0
4. 第四层处理节点13，保留数为0，直接返回null
5. 逐层返回拼接后，最终得到链表[10,11,12]，符合预期。

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