java - 使用递归/辅助函数计算链表的大小 - Java

Question

这里是使用 Java 的初学者(一年级学生)，我无法让以下功能正常工作。目标是使用递归和辅助函数来计算单链表的大小。当针对测试列表运行代码时，它会不断返回 List 更改为 []。

我在 Java 方面遇到了困难，所以非常感谢您的帮助。谢谢

public class MyLinked {
  static class Node {
   public Node(double item, Node next) {
    this.item = item;
    this.next = next;
   }
   public double item;
   public Node next;
  }
  int N;
  Node first;

  public int sizeForward() {
   return sizeForwardHelper(first);
  }

  public int sizeForwardHelper(Node n) {
   Node current = first;
   if (current == null) {
    return 0;
   } else {
    first = first.next;
    return sizeForward() + 1;
   }
  }

我相信如果列表中没有元素，我将第一部分设置为返回 0。我相信这是第二部分设置不正确？

谢谢

Answer 1

因为不要用勺子喂你，这对你的学习很重要，所以我将描述一种方法而不是提供代码。

使用这个事实:

The length of the list from any given node to the end is 1 plus the length measured from the next node (if there is one).

通常(就像在这里一样)，递归函数采用这种形式:

1. 如果终止条件为真，则返回一些值
2. 否则，返回一些值加上递归计算的值

编写递归函数时，首先要确定终止条件。在这种情况下，n == null 是显而易见的选择，并且您将返回 0，因为您已经超出了列表的末尾并且没有任何长度(即没有节点)什么都没有。这也可以处理空列表(当 first 为 null 时)，无需任何特殊代码。

否则，返回1(一个节点的长度)加上next的长度。

把所有这些放在一起，你就会得到答案。

——

提示:如果使用三元表达式，则可以使用一小行代码对递归辅助方法的主体进行编码。