algorithm - 向后读取链表而不改变它

Question

给定一个单向链表，向后读取该链表。这听起来是个简单的问题但是(!)你不能改变链表的指针，你只能使用 3 个变量(指针或其他变量)，每个单元格都有一个以 false 开头的 bool 标志，你可以使用它如你所愿。

在 O(n^2) 中很容易做到，但我认为有更好的解决方案(也许是 O(n)？)。

Answer 1

这种递归方法只对列表迭代 1 次。所以它是 O(n)。

它是如何工作的:

它递归遍历列表，直到到达末尾，然后将方法调用添加到栈帧中。最后它打印出最后一个节点并返回到第二个最后的方法调用(它通过堆栈框架返回)

void RecursiveBackwardPrint(node* node)
{
    if(node->next != nullptr)
    {
        RecursiveBackwardPrint(node->next);
    }
    std::cout<<node->value<<std::endl;
}