包含（int aData）和递归链表 Java

Question

我在尝试检查某个值是否在链表中或未使用递归时遇到问题。链表中的值介于 0 和 5 之间。如果值在链表中，则该方法应 return 为真。但是，如果该值确实在链表中，我会得到全面的答案。有些数字 return 为假，有些数字 return 为真。我不确定为什么要这样做。谢谢！

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

Answer 1

如前所述，您没有使用递归，只是检查第一个节点。如果你想使用递归，你需要从 contains 方法中调用 contains 方法，你目前没有这样做。即使你只是像现在这样在方法的末尾调用它，它仍然不会做任何事情 - 想想如果方法开始你可能如何重写它：

public boolean contains(int aData, Node nodeToCheck)

Answer 2

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

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 3

递归有一个非常明确的形式，几乎在所有情况下都会使用。本质上的形式是：

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

其工作原理是逐步将问题分解成更小的部分，直到问题简单到有明显的答案（即基本情况）。使用递归的关键是问自己 'in what situations is the answer obvious?'（即基本情况）和“当答案不明显时，我如何简化情况使其更明显？”。在回答这些问题之前不要开始编码！

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

将所有这些放在一起你有：

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);
}

包含（int aData）和递归链表 Java

contains(int aData) with Recursion Linked List Java

java

recursion

linked-list