你能在 O(1) 的运行时间内翻转一个栈吗？

Question

你能在 O(1) 的运行时间内翻转一个栈吗？

cstackbig-o

3

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

1 -> 2 -> 3 -> 4

变为

4 -> 3 -> 2 -> 1

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

有人可以推荐一种合理的解决方法吗？

- October171

9

为什么不直接存储一个方向标志呢？这样反转就是翻转方向标志。 - R.. GitHub STOP HELPING ICE

@R..GitHubSTOPHELPINGICE，你能详细说明一下吗？ - October171

不要使用 ->prev 和 ->next 成员，而是使用 ->link[2]，并将其作为 ->link[direction] 和 ->link[1-direction] 访问。 - R.. GitHub STOP HELPING ICE

“双向链接”列表实际上可以通过在每个列表项中存储一个包含其两侧节点的按位异或的单个uintptr_t来实现。当遍历列表时，如果前一个节点是P，当前节点是C，则下一个节点是(struct ListItem *) ((uintptr_t) P ^ C->RecordedXOR)，无论您在哪个方向上遍历列表。因此，通过交换头和尾记录，该实现具有O（1）翻转时间。不需要方向标志，并且不需要调整节点指针的索引。 - Eric Postpischil

@EricPostpischil：虽然异或链表是一种不错的数据结构，但它比双向链表更弱（你不能从列表中的任何项开始到达任何地方），对于非专业的C语言使用者来说，这是一种相当笨拙和容易出错的东西。 - R.. GitHub STOP HELPING ICE

@R..GitHubSTOPHELPINGICE：但它的优点在于更有趣，这显然比其他考虑因素更重要。 - Eric Postpischil

3个回答

1

定义一个新的结构体，指向链表尾部，并且交换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;
}

- ssd

0

如果您正在使用头和尾指针，通过交换这些指针应该足够了。这可以在O(1)时间内完成。

- Marceeaax

1

就像交换阅读方向一样，而不是实际重写指针。 - tadman

1

这本身还不够：头指针会指向列表中的最后一个元素，但下一个元素会结束列表。 - Weather Vane

1

我不相信这个解决方案本身就足够。如果您交换头和尾指针，那么链接列表中下一个/上一个链接的相对顺序将指向错误的方向，您需要跟踪额外的位以知道是否是这种情况。 - templatetypedef

如果节点有一个包含指向下一个和上一个节点的两个指针的二元数组，那么可以通过方向标志或 ! 方向标志进行索引，以便沿着另一条路径前进。 - Weather Vane

你也可以将头部指针和尾部指针设置为一个包含2个元素的数组的元素，通过方向标志或!方向标志进行索引。 - Weather Vane

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- R.. GitHub STOP HELPING ICE · Accepted Answer

只需将方向标志存储为列表的全局变量，并翻转它以翻转列表的方向。将列表节点定义为类似以下内容：

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

每个节点的dir指针应该指向整个列表共享的单个bool对象（例如在单独分配的内存中）。然后，无论您通常会访问p->next或p->prev，都应改为访问p->link[*p->dir]或p->link[!*p->dir]。现在，只需反转方向标志即可翻转整个列表的prev和next意义：*p->dir =！*p->dir。

请注意，将指针存储在每个节点中有一定成本，您可以通过将标志单独保留“离线”来避免这种情况，但这会限制您仅在具有该离线信息的位置访问列表（至少具有当前方向知识）；您不能从列表的某个成员开始执行此操作。