链表中的最小值.递归结果不正确

本文关键字：结果 不正确 递归 最小值 链表 | 更新日期: 2023-09-27 17:58:27

尝试复习一些概念。我试图在链表实现中的所有节点中找到最小值。我想出于某种原因，我的代码将返回所有递归返回值，而不是只返回最后一个。有人能检查一下我的findMin方法中的问题吗？

public class Node
{
    public int data;
    public Node next;
    public Node(int d)
    {
        data = d;
        next = null;
    }
}

public static int findMin(Node head,int min=0)
{
    if (min == 0)
        min = head.data;
    if (head.data < min)
    {
        min = head.data;
    }
    else
    {
        findmin(head.next, min);
    }
    return min;
}

链表中的最小值.递归结果不正确

我相信它会返回第一个元素。或者有时崩溃。

if (min == 0) min = head.data; //true initially. min=first element
if (head.data < min) //false. We just assigned it, it does not get executed
{
    min = head.data;
}
else
{
    findmin(head.next, min); //this gets executed but result is ignored
}
return min; // return head.data that you assigned in the first line

这是非常坏的。

  1. 您忘记将findmin（head.next，min）的结果分配给任何

  2. 即使head.data<min你仍然需要检查列表所以不需要"else"

  3. 您忘记检查列表是否为空

  4. 初始值应为int.MaxValue。不是0，也不是10000如上所述。那么你就不需要这个额外的比较了（因为任何东西都小于100000）

  5. 最好将递归调用放在最后，让编译器（或JIT）用循环替换尾部递归。或者自己写一个循环。

以下是

public static int findMin(Node head,int min=int.MaxValue)
{
     if (head == null) return min;
     if (head.data < min) min = head.data;
     return findmin(head.next, min);
}

findmin的递归调用的响应从未分配给min。因此，像min = findmin(head.next, min);一样调用它应该可以解决的问题

一些问题：1.通过值传递min2.min初始化为0。

试试这个

public static int findMin(Node cur) {
    if (cur == null) return 1000000;
    int next_min = findMin(cur.next)
    if (cur.data < next_min) return cur.data;
    return next_min;
}

这里最好不要使用递归来节省stack内存。只需使用while循环并找到最小值。

相关文章：