在链表中查找节点并返回索引

Question

下面的代码没有为以下输入返回正确的输出10 20 20 30 -1表示搜索元素40(n=40(。代码中的逻辑错误是什么。

public class Solution {
static int c=0; 
public static int indexOfNRec(LinkedListNode<Integer> head, int n) {
if(head.next==null )
{
return -1;
}
if(head.next==null && head.data!=n)
{
return -1;
}
if(head.next==null && head.data==n)
{
return 0;
}
if(head.data==n)
{
return c;
}
c=c+1;
indexOfNRec(head.next,n);
return c; 
} 
}

Answer 1

你已经让这种方式变得比它需要的更难。尝试这样的事情：

public class Solution {
public static int indexOfNRec(LinkedListNode<Integer> head, int n) {
return solution(head, n, 0);
}
private static int solution(LinkedListNode<Integer> head, int searchFor, int index) {
if(head == null )
{
return -1;
}
if(head.data == searchFor)
{
return index;
}
return solution(head.next, searchFor, index + 1);
} 
}

我想你的老师告诉你使用的方法的签名。请注意，以您的方式使用静态变量真的很丑陋，因为它在多线程环境中不起作用。此外，由于您永远不会清除它们，因此这是一个一次性工作的解决方案。如果您多次被调用，您将在第一次调用后获得错误的值。

所以我保留了你原来的方法签名，但把它链接到一个接收你要返回的索引的方法。这消除了静态变量，该变量使您的代码可重入 - 线程安全且可多次使用。

该方法本身非常简单。执行空检查并在空时返回。否则，如果我们找到数据，那就太好了。返回。如果没有，请递归。

这是一个需要理解的重要模式。请确保您知道它在做什么，并确保使用各种值进行测试。我没有通过编译器运行它，所以可能会有错误。但至少你可以看到我前进的方向。