java - 我想通过递归算法在链表中找到最大节点，但我的代码有问题

Question

如果我输入的链表数量为 3：x1 = 3，x2=1，x3=2 打印：2 1 3（确实如此）但 max=2，我找不到错误，这是我的代码：

int max(Node l){
    int max = 0;
    if(l == null) return 0;
    else
    {
        if(l.data > max){
            max = l.data;
            l = l.next;
        }                 
        else return max(l.next);
    }
    return max;
}
int max(){
    return max(head);
}

Answer 1

你的逻辑是错误的，因为你总是返回第一个元素的值（因为l.data > max永远是true，因为max总是0在这一点上）。

考虑递归查找最大元素的正确方法如下：

最大元素是第一个元素的最大值和列表其余部分的最大值。

IE

max(l) is the max of l.data and max(l.next)

所以你的方法应该是这样的：

int max(Node l)
{
    if(l == null) 
        return 0;
    else {
        int tailMax = max(l.next);
        return tailMax > l.data ? tailMax : l.data;
    }
}

int max(){
    return max(head);
}

Answer 2

通过编写显式尾递归函数的替代方法max

int max(Node l, int maximum)
{
    if(l == null) 
        return maximum;
    else {
        return max(l.next, l.data > maximum? l.data: maximum);
    }
}

int max(){
    return max(head, 0);//something small...
}