java - 自定义LinkedList:选择备用整数元素

我有一个Integer [21, 9, 13, 47, 5, 10, 19, 36, 20, 11, 13]的列表，我试图编写一个递归函数，该函数将返回原始列表中的所有其他整数作为列表（即[21, 13, 5, 19, 20, 13]）。

我正在使用LispList的自定义实现。该对象称为LispList，它是不可变的，（显然）没有索引。它提供以下方法：

E head（）-返回列表中被调用的第一项。
LispList tail（）-返回一个新列表，其中包括列表的第一项以外的所有项。
LispList cons（E item）-接受一个参数并返回一个新列表，其头是参数，而尾是要调用的列表。
boolean isEmpty（）-如果被调用的列表为空列表，则返回true，否则返回false。
静态 LispList empty（）-返回一个空列表。

经过数小时的尝试，我想出了一种使用初始化为2的计数器并使用它来跟踪偶数元素的方法，应该将其选中并放入新的LispList中并返回。

但是，当我运行代码时，它将引发NullPointerException，而我不明白为什么。也许我只是盯着屏幕太久了！

这是从main调用的方法：

public static <T> LispList<T> pickEveryOther(LispList<T> ls) {
        int counter = 2;
        LispList<T> ls1 = pickEveryOtherHelper(ls.tail(), counter);
        return ls1;
}

和辅助方法：

public static <T> LispList<T> pickEveryOtherHelper(LispList<T> ls, int counter) {
        LispList<T> wantLs = LispList.empty();
        if(ls.isEmpty()) {
            return LispList.empty();
        }
        else {
            if(counter % DIVIDER == 0) {
                // item we want
                wantLs = wantLs.cons(ls.head());
                counter++;
            }
            else {
                // don't want item, look in tail
                pickEveryOtherHelper(ls.tail(), counter);
            }
            return wantLs;
        }
    }

非常感谢您的努力。

最佳答案

解决方案是在每次递归中从列表中弹出2个值，并使用2个值之一构建新列表。

您没有真正指定“其他”是第1，第3，第5，...还是第2，第4，第6，...，所以这都是两个解决方案。

public static <T> LispList<T> pickOdd(LispList<T> ls) {
    if (ls.isEmpty())
        return ls; // return empty
    LispList<T> tail1 = ls.tail();
    if (tail1.isEmpty())
        return ls; // return of(ls.head())
    LispList<T> tail2 = tail1.tail();
    if (tail2.isEmpty())
        return tail2.cons(ls.head()); // return of(ls.head())
    return pickOdd(tail2).cons(ls.head());
}

public static <T> LispList<T> pickEven(LispList<T> ls) {
    if (ls.isEmpty())
        return ls; // return empty
    LispList<T> tail1 = ls.tail();
    if (tail1.isEmpty())
        return tail1; // return empty
    LispList<T> tail2 = tail1.tail();
    if (tail2.isEmpty())
        return tail1; // return of(ls.tail().head())
    return pickEven(tail2).cons(tail1.head());
}

为了测试它，我确实使用两个辅助方法（LispList和of(...)）实现了toString()：

final class LispList<E> {
    private final E           head;
    private final LispList<E> tail;
    private LispList(E head, LispList<E> tail) {
        this.head = head;
        this.tail = tail;
    }

    /** returns the first item of the list it is called on */
    public E head() {
        if (isEmpty()) throw new IllegalStateException();
        return this.head;
    }
    /** returns a new list consisting of all but the first item of the list it is called on */
    public LispList<E> tail() {
        if (isEmpty()) throw new IllegalStateException();
        return this.tail;
    }
    /** takes an argument and returns a new list whose head is the argument and whose tail is the list it is called on */
    public LispList<E> cons(E item) {
        return new LispList<>(item, this);
    }
    /** returns true if the list it is called on is the empty list, returns false otherwise */
    public boolean isEmpty() {
        return this.tail == null;
    }
    /** returns an empty list */
    public static <T> LispList<T> empty() {
        return new LispList<>(null, null);
    }

    @SafeVarargs
    public static <T> LispList<T> of(T ... values) {
        LispList<T> ls = empty();
        for (int i = values.length - 1; i >= 0; i--)
            ls = ls.cons(values[i]);
        return ls;
    }
    @Override
    public String toString() {
        StringJoiner joiner = new StringJoiner(", ", "[", "]");
        for (LispList<E> ls = this; ! ls.isEmpty(); ls = ls.tail())
            joiner.add(String.valueOf(ls.head()));
        return joiner.toString();
    }
}

测试

LispList<Integer> ls = LispList.of(21, 9, 13, 47, 5, 10, 19, 36, 20, 11, 13);
System.out.println("List: " + ls);
System.out.println("Odd : " + pickOdd(ls));
System.out.println("Even: " + pickEven(ls));

输出值

List: [21, 9, 13, 47, 5, 10, 19, 36, 20, 11, 13]
Odd : [21, 13, 5, 19, 20, 13]
Even: [9, 47, 10, 36, 11]