以递归方式返回链表中的元素数

Question

我在一个名为ImageNode的类中有以下递归方法,该类从名为Image的类传递头部(这是链接列表的开头).我以为我的代码将以递归方式遍历每个节点,增加计数,然后当它最后返回计数时,不幸的是没有.我哪里错了？

private int countRec() {
    int count = 1;
    ImageNode node = this;

    if (node.next != null ){
        node = node.next;
        count++;
        countRec();
    }

    return count;
}

Answer 1

你忽略了结果countRec()- 你在递归调用中迭代,打败了目的.(你也在对同一个对象进行递归调用,没有参数,状态也没有变化......所以不能做任何好事.)我的递归方法将基于以下设计:

• 如果下一个节点为null,则列表的大小为1
• 否则,大小为1 +从下一个节点开始的大小.

所以:

private int countRec() {
    return next == null ? 1 : 1 + next.countRec();
}

现在这不允许列表长度为0当然......你可能想要将列表的想法与节点分开,在这种情况下列表类将具有如下内容:

public int count() {
    return head == null ? 0 : head.countRec();
}

其中值head是对头节点的引用(如果有)或null其他.

当然,这将是时间和空间上的O(n).您可以使用迭代而不是递归来获得O(1)空间,并且通过将列表的大小保持为列表中的实例变量来获得O(1)时间,并在需要时更新它.我希望这个问题是基于教育要求而不是真正的代码 - 在生产代码中,你只需使用已经提供的集合.