java - 查找单链表的倒数第 k 个元素

Question

对于 Java 中的“单链表的第 k 到最后一个元素”问题，我有两个递归解决方案:

解决方案一:

public static Node nthToLast(Node head, int k , int i){
    if (head == null) return null;
    Node n = nthToLast(head.next, k, i);
    i = i + 1;

    if (i == k) return head;

    return n;
}

解决方案 2:

public class IntWrapper {
    public int value = 0;
}
public static Node nthToLast(Node head, int k, IntWrapper i){
    if (head == null) return null;
    Node n = nthToLast(head.next, k, i);
    i.value = i.value + 1;

    if (i.value == k) return head;

    return n;
}

第一个解决方案返回 null，而第二个解决方案完美运行。第一个解决方案按值传递 k，而第二个解决方案将 int 值包装在一个类中并传递它。

我有两个问题:

1. 为什么第一个解决方案在 Java 中不起作用？为什么在每个方法调用中通过局部变量 i 的按值传递与按引用传递版本的工作方式不同？

2. Java中的Integer类包装了int，但是将int替换为Integer第一个解决方案也不起作用。为什么？

Answer 1

1. 第一个解决方案不起作用，因为每次您在 i 变量中传递相同的值。如果将 i = i + 1 行移动到 Node n = nthToLast (head.next, k, i) 行上，一切都应该没有问题。
2. Integer 类是不可变的，因此表现得像普通的 int。这就是为什么如果您在第一个解决方案中使用 Integer 函数将无法正常工作。您可以替换我上面提到的第一个解决方案使用 Integer 的代码行。
第二种解决方案有效，因为递增计数器的方式不会覆盖对计数对象的引用。