0

我正在制作一个递归函数，它必须没有参数来获取链表的长度。

public int lengthHelper() {
    if (first == null) {
        return 0;
    } else {
        first = first.next;
        return 1 + length();
    }
}

问题是通过使用 first=first.next 我将首先破坏，首先是我的标题。所以我想先在函数中复制（而不是我丑陋的包装脚本），但递归使这很麻烦。知道如何进行吗？

这是包装器顺便说一句，我想删除它：

public int length() {
    Node temp = copy(first);
    int output = this.lengthHelper();
    first = copy(temp);
    return output;
}

我有这些限制的原因是因为这是基于任务的个人挑战。Recursive + wrapper 就足够了，但自从我一直在考虑是否有可能以更清洁的方式解决它。

4

3 回答 3

3

如果我理解正确first的是递归数据结构Node，并且在非递归容器类List（例如）中，您需要定义一个递归方法（不带参数）。

然后解决方案是有一种方法List可以产生一个新的尾部/休息列表，没有first. 下面我假设一个带有节点的构造函数。

class Node { }
public class List {
    Node first;

    public int length() {
        if (first == null) {
            return 0;
        } else {
            List tail = new List(first.next);
            return 1 + tail.length();
        }
    }
于 2013-09-17T17:25:37.837 回答
2

这是一个相当人为的要求。:) 但是存储first在本地堆栈帧中，然后在返回之前恢复它呢？

这听起来像是一个家庭作业问题，所以也许我不应该说出完整的答案。但它基本上是这样的：

  • 创建一个局部变量来存储当前值first
  • update first，从而打破了列表（正如你所指出的）
  • 向下递归，并将该递归的结果保存在第二个局部变量中
  • 使用第一个局部变量来恢复first
  • 从第二个局部变量返回结果

如果您碰巧在过程中遇到异常（例如堆栈溢出），请尝试以不会破坏列表的方式执行此操作。提示：try-finally。

于 2013-09-17T17:18:30.977 回答
1

没有干净的方法可以做到这一点。我推荐这样的东西：

public int length() {
    return computeLength(this.first);
}
private int computeLength(Node node) {
    if (node == null) return 0;
    return 1 + computeLength(node.next);
}
于 2013-09-17T17:12:51.283 回答