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。

递归寻找最大元素的正确思路如下:

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

即

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);
}