java - 自定义链表: Picking alternate integer elements

Question

我有一个整数 [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。
static 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;
        }
    }

非常感谢您的努力。

Answer 1

这应该可以解决问题，只需获取头部，然后尝试获取尾部两次并递归即可。只需考虑这样一个事实:在每个尾部之后它可能会变成一个空列表。然后将 head 添加到递归结果的前面。

public static <T> LispList<T> everyOther(LispList<T> lispList) {
    if (lispList.isEmpty()) {
        return lispList.empty();
    }
    T head = lispList.head();
    LispList<T> tail = lispList.tail();
    if (!tail.isEmpty()) {
        tail = tail.tail();
    }
    tail = everyOther(tail);
    return tail.cons(head);
}