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

user_11689118 0
Viewed 140

I am building a program that uses a doubly linked list to build a stack. I am required to flip the stack, or reverse the order of it, with a runtime of O(1). For instance:

1 -> 2 -> 3 -> 4

becomes

4 -> 3 -> 2 -> 1

The fastest way I can think of uses O(N) as a runtime. By being required to use a runtime of O(1) all loops are out of the question, as they will all inevitably depend on the number of nodes in the stack.

Can anybody recommend a reasonable way to go about this problem?

stack big-o c
3 Answers

Just store a direction flag global to the list, and flip it to flip the direction of the list. Define your list node as something like:

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

Each node's dir pointer should point to a single bool object shared by the whole list (e.g. in separate allocated memory). Then wherever you would normally access p->next or p->prev, instead access p->link[*p->dir] or p->link[!*p->dir], respectively. Now you can flip the sense of prev and next for the whole list just by inverting the direction flag: *p->dir = !*p->dir;.

Note that there's a cost to storing a pointer in each node, and you can avoid this just by keeping the flag separately "out of band", but this limits you to accessing the list (at least with knowledge of current direction) only where you have that out-of-band information; you then can't do it starting just from a member of the list.

user_3798970

Defining a new struct pointing to the tail of the linked list with prev & next pointers switched (swapped) may help. This way, in fact, you do not even swap or move any data value but just look at the data stream with a different set of glasses.

edit: And yes, as @Marceeaax noted, you had to be keeping track of the head & tail pointers.

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

If you're using head and tail pointers, it should be enough by swapping those pointers. That would be done in O(1).

user_131127610
Related