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

如果我输入的链表的数量为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);
}
wangliqingkong 回答:我想通过递归算法在链表中找到最大节点,但是我的代码有问题

您的逻辑是错误的,因为您始终返回第一个元素的值(因为l.data > max始终为true,因为此时max始终为0 )。

考虑递归查找max元素的正确方法如下:

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

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

通过编写显式的tail-recursive函数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...
}
本文链接:https://www.f2er.com/3167984.html

大家都在问