java - Java 中链表的递归最大值

Question

为了学习递归并编写自定义链表(不是 java.util 中的 LinkedList)，我尝试创建一个递归 max() 方法如下。我不得不付出一些努力，但最终我成功了。但是，我不确定这是否是正确的方法(或最简单的方法)。一方面，我不太确定基本情况。我已将基本情况设置为列表中的最后一个节点。这是应该做的吗？请告诉我如何编写一个简单的递归最大值方法..

class ListNode{
    int item;
    ListNode next;
}

class RecursiveMax{    

    public static int max(ListNode node,int maxValue){
        //is this the base case ?
        //if last node reached return the current maxValue 
        if(node==null){
            return maxValue;
        }else{
            int v = node.item;
            if(v > maxValue){
                return max(node.next,v);
            }else{
                return max(node.next,maxValue);
            }
        }
    }
    public static void main(String[] args) {
        ListNode a = new ListNode();
        a.item = 11;

        ListNode b = new ListNode();
        b.item = 9;

        ListNode c = new ListNode();
        c.item = 21;

        ListNode d = new ListNode();
        d.item = 17;

        a.next = b;
        b.next = c;
        c.next = d;
        System.out.println("max value in linkedlist="+max(a,0));
    }

}

对于链表a-b-c-d(值为11,9,21,17) 输出为

max value in linkedlist=21

Answer 1

好吧，您将在 main 中以 0 作为当前最大值开始搜索。当所有值都是负时会发生什么？

我认为你可以做得更好。使用两个参数 private 调用 max 方法。然后，公开仅接受 ListNode 的 max。

public static int max(ListNode node) {
    //max value is its value.
    if (node == null) {
        return Integer.MIN_VALUE;
    }
    return max(node, node.item);
}

private static int max(ListNode node,int maxValue){
    int v = node.item;
    if(v > maxValue){
        return max(node.next,v);
    }else{
        return max(node.next,maxValue);
    }
}

最后，在 main 中，您只需调用 max(a);