c - 你可以翻转一个运行时间为 O(1) 的堆栈吗？

Question

我正在构建一个使用双向链表来构建堆栈的程序。我需要翻转堆栈或反转堆栈的顺序，运行时间为 O(1)。例如：

1 -> 2 -> 3 -> 4

变成

4 -> 3 -> 2 -> 1

我能想到的最快方法使用 O(N) 作为运行时。由于需要使用 O(1) 的运行时间，所有循环都是不可能的，因为它们都不可避免地取决于堆栈中的节点数量。

任何人都可以推荐一个合理的方法来解决这个问题吗？

标签： cstackbig-o

Answer 1

只需将一个方向标志全局存储到列表中，然后翻转它以翻转列表的方向。将您的列表节点定义为：

struct node {
    struct node *link[2];
    bool *dir;
};

每个节点的dir指针应指向bool整个列表共享的单个对象（例如，在单独分配的内存中）。然后，无论您通常访问p->nextor p->prev，而不是访问p->link[*p->dir]or p->link[!*p->dir]，分别。现在你可以通过反转方向标志来翻转整个列表的 prev 和 next 的感觉：*p->dir = !*p->dir;。

请注意，在每个节点中存储一个指针是有代价的，您可以通过将标志单独保持“带外”来避免这种情况，但这会限制您仅在您访问列表的情况下（至少在了解当前方向的情况下）拥有带外信息；然后，您不能仅从列表的成员开始执行此操作。