CODEWITHSUNDEEP
c++algorithmdata-structures
Hemant Bhargava
Hemant Bhargava

Reputation: 3585

Linked list reverse without using the loop?

I was asked by one of my senior executives that is it possible to reverse an singly linked list without using an loop? If yes, how? His smile seemed to tell me that it is possible but I could not think of anything. Anyone thought about this earlier?

Upvotes: 2

Views: 1064

Answers (3)

neuront
neuront

Reputation: 9622

An approach in recursion

struct node {
    int value;
    struct node* next;
};

struct node** _reverse(struct node* n)
{
    if (NULL != n->next)
        *_reverse(n->next) = n;
    return &(n->next);
}

// this is the entry
void reverse(struct node* head)
{
    *_reverse(head) = NULL;
}

Upvotes: 2

Zefick
Zefick

Reputation: 2119

In STL there is rbegin() and rend() iterators for traversing collections in reverse order. But it will not work for single linked list.

Upvotes: 1

SingerOfTheFall
SingerOfTheFall

Reputation: 29966

It is possible to reverse a double-linked list in O(1) by swapping it's head and tail pointers, and (depending on the implementation) setting some kind of a flag that will tell that the list should be now iterated backwards (i.e. following the back pointers to iterate forward, and following the next pointers to iterate backward).

As for a single-linked list, I believe it's impossible to reverse it faster than O(n).

Upvotes: 4

Related Questions