java - 我应该如何为 LinkedList 定义 contains() 命令？

Question

我目前正在通过递归重新定义链表的命令，其中公共(public)方法接受一个对象并调用私有(private) contains() 方法，该方法具有 Node 参数，但似乎无法弄清楚逻辑。

@Override
public boolean contains(Object o) {
    if (o.equals(contains(o))) {
        return true;
    }

    contains(o);
    return false;
}

private boolean contains(Node node) {
    if (node.next == null) {
        return false;
    }

    if (node == node.next) {
        return true;
    }

    return contains(node.next);
}

Answer 1

假设您被迫使用递归(而不是迭代)，让我们看看您在这里需要什么:

1. 私有(private)递归方法

递归方法必须有一个基本情况和一个子问题的递归调用(在本例中是列表的其余部分)。

a) 基本情况:在此处的基本情况中，您要么找到具有预期键的节点，要么到达列表的末尾，如下所示:

if (node == null) {
    return false;
}

if (key.equals(node.key)) {
    return true;
}

b) 递归调用:您必须使用next 节点(列表的其余部分)调用该方法。

return contains(key, node.next);

将两者放在一起，您将得到以下方法:

private boolean contains(Object key, Node node) {

    if (node == null) {
        return false;
    }

    if (key.equals(node.key)) {
        return true;
    }

    return contains(key, node.next);
}

公共(public)方法

公共(public)方法只需要一个键并调用指向列表头部的节点的递归方法。

@Override
public boolean contains(Object o) {
    returns contains(o, this.head);
}

如果您按照上述模板练习一些简单的递归问题，以掌握一些知识，将会很有帮助。