向后读取链表而不更改它

Question

给定一个单向链表，向后读取列表。这听起来像是一个简单的问题，但是（！）你不能改变链表的指针，你只能使用3个变量（指针或其他变量），每个单元格都有一个以false开头的布尔标志，你可以随心所欲地使用它。

在 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;
}

Answer 2

您可以在 O（n） 中通过每次组合 32 个布尔值来将它们转换为指向前一个 32 个元素块的指针。

算法：

• 读取列表的最后元素以使列表大小 % 32。（O（n*32） = O（n））
在元素 32 到 63 中使用布尔值存储指向开头的指针，
• 在元素 64 到 95 中使用布尔值存储指向元素 32 的指针，依此类推 （O（n））
转到最后 32 个块 （O（n）），读取它们 （O（32）），跳回到最后 64 个块 （O（1）），按倒序读取接下来的 32 个块 （
• O（32）），跳回到最后 96 个块，依此类推。

它是 O（n），但至少需要 32*n 次操作，只值得用于很长的列表。