如何制作递归单链表（C++）[已关闭]

Question

我的书要求我对单链表进行递归定义。我完全不知道该怎么做。有人可以帮我提供样品吗？谢谢

Answer 1

它就像一个普通的链表，只不过迭代是通过递归而不是循环来执行的。

首先，简单阅读一下：什么是递归以及何时应该使用它？

例如，查找最后一个节点的基于循环的函数可以是：

Node * getLast(Node * current)
{
    while (current->next)
    { // loop until no more nodes
        current = current.next;
    }
    return current; // return last node
}

而递归版本只检查当前节点是否是最后一个节点，如果有下一个节点，则用下一个节点调用自身。

Node * getLast(Node * current)
{
    if (current->next)
    { // see if next node is last node
        return getLast(current->next);
    }
    else
    { // found last node. return it
        return current;
    }
}

请注意，这两种方法都要求

current

处的列表不为空。