我的递归查找(T数据)方法正在调整LinkedList的大小.我该如何停止它

Question

我需要为LinkedList制作一些使用递归的方法。我有一些很好的，但这是给我带来麻烦的一个：

public boolean find(T data){    
    if(head == null)
        return false;
    else{
        if(head.data == data)
            return true;
        else{
            head = head.next;
            return find(data);
        }
    }
}

它应该在LinkedList中找到一个元素，但问题是，List不应该被附加，这显然是随着头部位置的增加。原型应该有一个参数，数据一个。我怎样才能让它停止增加头部位置？

Answer 1

您需要维护对当前节点的单独引用；不要使用CCD_ 1。我会使用helper方法来完成此操作。

public boolean find(T data){    
    return find(data, head);
}
private boolean find(T data, Node current) {
    if (current == null) return false;
    if (current.data.equals(data)) return true;
    current = current.next;
    return find(data, current);
}

请注意，在比较data值时使用.equals()而不是==。我假设head属于Node类。如果这不是正确的猜测，请填写实现中的实际类。

Answer 2

除非您的需求在使用递归时很严格，否则我建议您使用迭代遍历列表。递归的效率很低，因为它会创建不必要的函数堆栈。

递归可用于简化非线性遍历或数据结构的代码。

相同使用迭代的代码如下所示。

public boolean find(T data) {
    boolean found = false;
    T current = head;   
    while(current != null) {
        if(current.data.equals(data)) {
            found = true;
            break;
        }
        current = current.next;
    }
    return found;
}