为什么使用递归时无法返回 Java 链表遍历中的对象？

Question

在《破解编码访谈（第6版）》一书中，一个问题要求我：

实现一种算法来查找单向链表的第 k 个到最后一个元素

后来，作者声称：

不幸的是，我们不能使用正常的返回语句传回节点和计数器。

她在上面的声明中指的是Java语言。她后来表明，在 Java 中，我们只能打印单向链表中最后一个元素的第 k 个。

我的问题是：为什么当递归弹出帧时我们不能传回节点？为什么我们不能在递归函数中添加另一个参数，以便在正确的时间（即当索引 = 第 k 项时）将该参数设置为我们正在寻找的节点？从昨晚开始，我一直在想这个问题，我就是想不通。

提供的示例答案如下所示：

int printKthToLast (LinkedListNode head, int k) {
    if(head == null) {
        return 0;
    }
    int index = printKthToLast(head.next, k) + 1;
    if (index == k) {
        System.out.println(k + "th to last node is " + head.data);
    }
    return index;
}

Answer 1

当你

说我们可以"向递归函数添加另一个参数，以便在正确的时间设置参数"时，你是对的。例如，此函数的工作方式与您发布的解决方案相同：

private void printKthToLast(LinkedListNode head, int k, int index) {
    if(head == null) {
        return;
    }
    if(index >= k) {
        System.out.println(head.data);
    }
    printKthToLast(head.next, k, ++index);
}

我的猜测是，作者试图说明递归通常"将问题划分为子问题，解决这些子问题，并组合结果"（即经典的分而治之方法）。在这种情况下，当我们在"next"元素上调用递归函数时，会将问题划分为子问题，因为我们越来越接近基本情况（head == null）。要合并的结果是索引，必须递归递增以确定何时必须打印节点。这就是索引建立函数的返回类型 （int） 的原因。这是递归解决问题的正确方法。你建议的是可能的，但将"索引"作为参数传递既不是将问题划分为子问题，也不是将结果组合在一起。

此外，同样重要的是要考虑到，在 Java 中，方法不仅由其名称标识，还由其输入参数、返回类型等标识。所以，这两种方法...

private int printKthToLast(LinkedListNode head, int k)
private void printKthToLast(LinkedListNode head, int k, int index)

。是完全不同的，即使它们具有相同的名称（这称为多态性）。因此，在同一解决方案中包含这两种方法不会是递归。

Answer 2

LinkedListNode由

LinkedList内部使用。

LinkedList上没有允许检索内部LinkedListNode（实际上称为Entry）的公共方法。

因此，给定一个LinkedList，您无法访问内部节点。

但是，如果只是浏览列表，您可以简单地使用迭代器并递归它：

int printKthToLast (Iterator<E> it, int i) {
    if(!it.hasNext()) {
       return 0;
    }
    E e = it.next();
    // ...
}