在《破解编码面试》(第6版)一书中,一个问题要求我:
实现算法以查找单链表的第k个元素
后来,作者声称:
不幸的是,我们无法使用普通的return语句传回节点和计数器。
她在上述声明中指的是Java语言。稍后,她将展示我们只能在Java单链表中将第k个元素打印到最后一个元素。
我的问题是:为什么递归弹出框架时我们为什么不能传递回节点?为什么我们不能在递归函数中添加另一个参数,以使该参数在正确的时间(即index = kth item时)设置到我们要查找的节点?自昨晚以来,我一直在考虑这个问题,但我无法将其包裹住。
提供的示例答案如下所示:
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;
}
最佳答案
当您说我们可以“将另一个参数添加到递归函数,以便在正确的时间设置该参数”时,您是对的。例如,此功能与发布的解决方案的工作方式相同:
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)
...完全不同,即使它们具有相同的名称(这称为多态)。因此,将这两种方法包含在同一解决方案中将不会递归。
关于java - 使用递归时,为什么不能在Java链表遍历中返回Object?,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/34793348/