包含(int aData)和递归链表Java

Question

我在检查值是否在链表中时遇到问题，或者是否使用递归。链接列表中的值介于0和5之间。如果该值在链表中，则该方法应返回true。然而，如果值确实在链表中，我会得到全面的疯狂答案。有些数字将返回false，有些则返回true。我不知道它为什么这么做。谢谢

public boolean contains(int aData)
{
    Node currentNode = firstNode;
    if(currentNode == null) {
        return false;
    }
    if(currentNode.data == aData) {
        return true;
    }
    else {
        return false;
    }
}

Answer 1

您只检查了一个节点（第一个节点）。你将需要这样的东西：

public boolean contains(int aData, Node node)
{
    Node currentNode = node;
    // base case; if this node is null, return false
    if(currentNode == null) {
        return false;
    }
    // if this node contains the data, return true, otherwise, check next nodes.
    if(currentNode.data == aData) {
        return true;
    } else {
        return contains(aData, currentNode.next);
    }
}

您可以从头节点开始调用上述函数

contains(5, headNode);

它将运行整个列表，直到a）找到数据，或者b）用尽所有选项，但没有找到数据。

Answer 2

如前所述，您没有使用递归，只检查第一个Node。如果您想使用递归，您需要从contains方法中调用contains方法，而您目前没有这样做。即使你只是在方法的末尾调用它，它仍然不会起任何作用——想想如果方法启动了，你可能会如何重写它：

public boolean contains(int aData, Node nodeToCheck)

Answer 3

Recursion有一个定义良好的形式，几乎在所有情况下都可以使用。本质上，形式是：

type method(context) {
    if (one of the base cases holds)
        return appropriate base value
    else
        for each possible simpler context
            return method(simpler context);
}

这是通过逐步将问题分解为更小的部分来实现的，直到问题变得如此简单，以至于有了明显的答案（即基本情况）。使用递归的关键是问自己"在什么情况下答案是显而易见的？"（即基本情况）和"当答案不明显时，我如何简化情况以使其更明显？"。在你能回答这些问题之前，不要开始编码！

在您的案例中，您有两个基本情况：您已经到达列表的末尾，或者您已经找到了值。如果这两种情况都不成立，请在更简单的上下文中重试。在您的案例中，只有一个更简单的上下文：一个较短的列表。

把所有这些放在一起：

public boolean contains(Node node, int data) {
    if (node == null)
        return false;
    else if (node.value == data)
        return true;
    else
        return contains(node.next, data);
}