Как мне определить команду contains () для LinkedList?

Question

В настоящее время я переопределяю команды для связанного списка с помощью рекурсии, где открытый метод принимает объект и вызывает закрытый метод 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. Частный рекурсивный метод

У рекурсивного метода должен быть базовый случай и рекурсивный вызов для подзадачи (в данном случае остальная часть списка).

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

Открытый метод

Открытый метод просто берет ключ и вызывает рекурсивный метод с узлом, указанным на начало списка.

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

Было бы полезно, если вы попрактикуетесь в нескольких простых задачах по рекурсии, следуя приведенному выше шаблону, просто для ознакомления с вещами.