java - 自制类的递归indexOf()方法

Question

我得到了一个 List 类(此处: http://pastebin.com/ZCi3q7LQ )，并且必须为其编写一些方法，包括查找指定整数索引的方法。

索引从零开始，如果指定的整数不在列表中，该方法必须返回 -1，该方法必须递归工作并在 $O(n)$ 时间内运行。

我的问题是在为不在平凡列表中的整数调用indexOf 时使该方法返回-1。我尝试了几乎所有可能的组合，并在这里阅读了一些类似的问题，但它们没有帮助。这是我做的:

public int indexOf(int x) {
    return indexOf(x, first);   
}

private static int indexOf(int x, Node n) {
    if (n==null) {
        return -1;
    }
    else if (n.data==x) {
        return 0;
    }
    else return 1+indexOf(x, n.next);
}

如果 x 不在列表中并且列表非空，这将返回最后一个元素的索引，这不是预期的。就像我说的，我完全不知道如何完成这项工作，我将不胜感激任何我能得到的帮助。

(如果重要的话，是的，这是作业。)

Answer 1

问题是当它返回堆栈时，它总是在返回值上加一，包括负数。虽然添加检查以查看返回是否为 -1 很容易，但还有一个更简单的解决方案。

public int indexOf(int x) {
    return indexOf(x, first, 0);   
}

private static int indexOf(int x, Node n, int depth) {
    if (n==null) {
        return -1;
    }
    else if (n.data==x) {
        return depth;
    }
    else return indexOf(x, n.next, depth + 1);
}