你能用 O(1) 的运行时间翻转堆栈吗？

Question

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

1 -> 2 -> 3 -> 4

变成

4 -> 3 -> 2 -> 1

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

谁能推荐一个合理的方法来解决这个问题？

Answer 1

如果您使用头指针和尾指针，交换这些指针应该就足够了。这将在 O(1) 中完成。

Answer 2

用 prev 和 next 指针切换（交换）定义一个指向链表尾部的新结构可能会有所帮助。这样，实际上，您甚至不需要交换或移动任何数据值，而只需用另一副眼镜查看数据流。

编辑：是的，正如@Marceeaax 指出的那样，您必须跟踪 head 和 tail 指针。

typedef struct OriginalStruct {
    SomeType value;
    ...
    OriginalStruct *prev;
    OriginalStruct *next;
} OriginalStruct;

typedef struct ReversedStruct {
    SomeType value;
    // all same but the last two switched / swapped
    ReversedStruct *next;
    ReversedStruct *prev;
} ReversedStruct;

...
int main() {
    OriginalStruct *orgnHead = NULL;
    OriginalStruct *orgnTail = NULL;
    OriginalStruct *orgnList = createList(&orgnHead, &orgnTail);

    ...
    ReversedStruct *rvsdList = orgnTail;

    ...
    return 0;
}

Answer 3

只需要在链表中存入一个全局的方向标志，翻转它就可以翻转链表的方向。将您的列表节点定义为：

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

每个节点的 dir 指针应指向整个列表共享的单个 bool 对象（例如，在单独分配的内存中）。然后在您通常访问 p->next 或 p->prev 的任何地方，分别访问 p->link[*p->dir] 或 p->link[!*p->dir]。现在你可以通过反转方向标志来翻转整个列表的上一个和下一个的意义：*p->dir = !*p->dir;.

请注意，在每个节点中存储一个指针是有成本的，您可以通过单独保留标志来避免这种情况"out of band"，但这限制了您访问列表（至少在了解当前方向）只有在你有带外信息的地方；然后你不能只从列表中的一个成员开始。

你能用 O(1) 的运行时间翻转堆栈吗？

Can You Flip a Stack with a Runtime of O(1)?

c

big-o

stack