java - 在Java中使用递归查找双链表中的最小元素

Question

类分配要求我编写具有指定方法签名的方法:

 public static <T extends Comparable<T>> T findSmallest(DoubleLinkedListADT<T> list)

该方法必须返回列表中的最小元素，它必须递归，我不能修改方法签名，并且增长函数不能有大于 n 的大 O(O(nlogn) 是 Not Acceptable 。)

这是我目前所拥有的:

public static <T extends Comparable<T>> T findSmallest(DoubleLinkedListADT<T> list) {

    if(list.isEmpty()){
        return null;
    }
    ListIterator<T> lit = list.listIterator();
    T smallest = lit.next();

    return search(lit, smallest);
}

private static <T extends Comparable<T>> T search(ListIterator<T> lit, T smallest){

    if(lit.hasNext()){
        if(smallest.compareTo(lit.next())==1){
            smallest =  lit.previous();
            lit.next();
        }
        search(lit, smallest);
    }
    return smallest;
}

(不用担心 DoubleLinkedListADT，它是老师提供的接口(interface)。可以将 DoubleLinkedList 引用分配给 DoubleLinkedListADT 类型，它是它的子类型。)

这适用于空列表、单元素列表和双元素列表。任何更大的东西都会失败。我想我只是不太了解递归，因为我对以下事实感到困惑:搜索方法中的第一个返回语句不是返回到 findSmallest 类中搜索调用的内容。它使用搜索中的最后一个返回调用，该调用使用第一个最小的错误最小对象引用。

我不是在找人给我正确的代码。我想弄清楚为什么它正在做它正在做的事情。

Answer 1

好吧，您的代码很复杂，所有双链接爬行看起来都很讨厌。这是我能为整数列表提供的最优雅的解决方案:

public class Test {

    public static Integer min(Iterator<Integer> it) {
        if (it.hasNext()) {
            return Math.min(it.next(), min(it));
        }
        return Integer.MAX_VALUE;
    }

    public static void main(String[] args) {
        System.out.println(min(Arrays.asList(2, 3, 1, 4, 5).iterator()));
    }
}

使它适应任何类型的列表应该很容易。