 # Reverse a doubly linked list in O(1)

Is it possible to reverse a doubly linked list in O(1) time ? I browsed the web but the answer was not clear.
This is a snippet from a solution

void quick_reverse()
{
node* temp = tail;
}

Is this a correct way of doing?

1 Like

A simple method for reversing a Doubly Linked List is to do swap prev and next pointers for all nodes, change prev of the head (or start) and change the head pointer in the end.

In the context of the above idea, your function is not completely correct as it only changes the tail and head pointer.

It is possible to reverse a doubly linked list in O(n) time and
a simple function to do so is as shown `void` `reverse(Node **head_ref) `

`{ `

` ` `Node *temp = NULL; `

` ` `Node *current = *head_ref; `

` ` `/* swap next and prev for all nodes of `

` ` `doubly linked list */`

` ` `while` `(current != NULL) `

` ` `{ `

` ` `temp = current->prev; `

` ` `current->prev = current->next; `

` ` `current->next = temp; `

` ` `current = current->prev; `

` ` `} `

` ` `/* Before changing the head, check for the cases like empty list and list with only one node */`

` ` `if` `(temp != NULL ) `

` ` `*head_ref = temp->prev; `

`} `

Don’t forget to like and give review to the answer
keep coding, stay healthy
cheers !!

3 Likes

Appreciate ur efforts but my question was if it is possible to do it in O(1) time.
For reference, the full sol. ,
https://codeforces.com/contest/1382/submission/87615344

Ohh !! I just forgot to answer the main question A memory efficient doubly linked list with head and tail pointers can also be reversed in O(1) time by swapping head and tail pointers.
But we would have to traverse the list in forward direction using prev pointer and reverse direction using next pointer which may not be considered valid.

Thats what i found on the web but is the final ans YES or NO? If yes, how?

Okay The final answer is yes you can do but you have to change the meaning of prev and next pointers which may not fit completely into your code.

is that what is done in this sol.
https://codeforces.com/contest/1382/submission/87615344

If you can maintain Head and Tail pointer,

and which case, Head is the forward way of traversing the LL and Tail is the reverse way.

If you want to reverse the DLL in O(1), swap Head and Tail

1 Like

why? Doubly LL maintains both frwd and backward

@chef_ka_baap Yes the same thing is done in this solution.

Here’s a very, very rough implementation - it’s still buggy (the case where an iterator is still alive when the list is reversed is very unlikely to be implemented correctly, and I can’t be bothered just now XD) and I haven’t added `operator--`, but it could probably be knocked into shape quite easily - I’ll leave that as an exercise ``````#include <iostream>
#include <list>
#include <cassert>

using namespace std;

template <typename T>
{
private:
class Node;
public:
void push_back(const T& value)
{
if (!m_isReversed)
m_list.push_back(value);
else
m_list.push_front(value);
};
void quickReverse()
{
m_isReversed = !m_isReversed;
}
friend class Iterator;
class Iterator
{
public:
Iterator(const Iterator& other)
: m_iter(other.m_iter),
m_containingList(other.m_containingList),
m_reachedEnd(other.m_reachedEnd)
{
}
Iterator& operator++()
{
if (!m_containingList.m_isReversed)
{
m_iter++;
if (m_iter == m_containingList.m_list.end())
m_reachedEnd = true;
}
else
{
if (m_iter == m_containingList.m_list.begin())
m_reachedEnd = true;
else
m_iter--;
}
return *this;
}
T& operator*()
{
assert(!m_reachedEnd);
return *m_iter;
}
const T& operator*() const
{
return *m_iter;
}

bool operator==(const Iterator& other) const
{
if (m_reachedEnd != other.m_reachedEnd)
return false;
if (m_reachedEnd)
return true;
return m_iter == other.m_iter;
}
bool operator!=(const Iterator& other) const
{
return !(*this == other);
}
private:
Iterator(typename std::list<T>::iterator iter, DoubleLinkedList& containingList, bool reachedEnd = false)
: m_iter(iter),
m_containingList(containingList),
m_reachedEnd(reachedEnd)
{
}
typename std::list<T>::iterator m_iter;
bool m_reachedEnd = false;
};
Iterator begin()
{
if (!m_isReversed)
return {m_list.begin(), *this};
else
return {std::prev(m_list.end()), *this};
}
Iterator end()
{
return {m_list.end(), *this, true};
}
private:
std::list<T> m_list;
bool m_isReversed = false;

};

int main()
{
mylist.push_back(1);
mylist.push_back(2);
mylist.push_back(3);
mylist.push_back(4);
mylist.push_back(5);
//auto blahIter = mylist.begin();
//cout << *blahIter << endl;
cout << "Original list: " << endl;
for (const auto& value : mylist)
{
cout << value << endl;
}

mylist.quickReverse();
cout << "After reverse: " << endl;
for (const auto& value : mylist)
{
cout << value << endl;
}

mylist.push_back(6);
cout << "After appending 6 to reversed: " << endl;
for (const auto& value : mylist)
{
cout << value << endl;
}

mylist.quickReverse();
cout << "After reversing again: " << endl;
for (const auto& value : mylist)
{
cout << value << endl;
}

mylist.push_back(7);
cout << "After appending 7: " << endl;
for (const auto& value : mylist)
{
cout << value << endl;
}

auto printIter = [&mylist](const auto iter)
{
if (iter == mylist.end())
cout << "<END>" << endl;
else
cout << "iterator pointing to: " << *iter << endl;
};

auto blahIter = mylist.begin();
++blahIter;
++blahIter;
cout << "After advancing two places: " << endl;
printIter(blahIter);

mylist.quickReverse();
++blahIter;
cout << "After reversing, then advancing one place: " << endl;
printIter(blahIter);

++blahIter;
cout << "After advancing one more place: " << endl;
printIter(blahIter);

++blahIter;
cout << "After advancing one more place: " << endl;
printIter(blahIter);

}
``````
5 Likes

The case where an iterator is still alive when the list is reversed is very unlikely to be implemented correctly, and I can’t be bothered just now XD.

using namespace std;

template
{
private:
class Node;
public:
void push_back(const T& value)
{
if (!m_isReversed)
m_list.push_back(value);
else
m_list.push_front(value);
};
void quickReverse()
{
m_isReversed = !m_isReversed;
}
friend class Iterator;
class Iterator
{
public:
Iterator(const Iterator& other)
: m_iter(other.m_iter),
m_containingList(other.m_containingList)
{
}
Iterator& operator++()
{
if (!m_containingList.m_isReversed)
{
m_iter++;
if (m_iter == m_containingList.m_list.end())
m_reachedEnd = true;
}
else
{
if (m_iter == m_containingList.m_list.begin())
m_reachedEnd = true;
else
m_iter–;
}
return this;
}
T& operator
()
{
assert(!m_reachedEnd);
return m_iter;
}
const T& operator
() const
{
return *m_iter;
}

``````            bool operator==(const Iterator& other) const
{
if (m_reachedEnd != other.m_reachedEnd)
return false;
if (m_reachedEnd)
return true;
return m_iter == other.m_iter;
}
bool operator!=(const Iterator& other) const
{
return !(*this == other);
}
private:
Iterator(typename std::list<T>::iterator iter, DoubleLinkedList& containingList, bool reachedEnd = false)
: m_iter(iter),
m_containingList(containingList),
m_reachedEnd(reachedEnd)
{
}
typename std::list<T>::iterator m_iter;
bool m_reachedEnd = false;
};
Iterator begin()
{
if (!m_isReversed)
return {m_list.begin(), *this};
else
return {std::prev(m_list.end()), *this};
}
Iterator end()
{
return {m_list.end(), *this, true};
}
private:
std::list<T> m_list;
bool m_isReversed = false;
``````

};

int main()
{
mylist.push_back(1);
mylist.push_back(2);
mylist.push_back(3);
mylist.push_back(4);
mylist.push_back(5);

``````cout << "Original list: " << endl;
for (const auto& value : mylist)
{
cout << value << endl;
}

mylist.quickReverse();
cout << "After reverse: " << endl;
for (const auto& value : mylist)
{
cout << value << endl;
}

mylist.push_back(6);
cout << "After appending 6 to reversed: " << endl;
for (const auto& value : mylist)
{
cout << value << endl;
}

mylist.quickReverse();
cout << "After reversing again: " << endl;
for (const auto& value : mylist)
{
cout << value << endl;
}

mylist.push_back(7);
cout << "After appending 7: " << endl;
for (const auto& value : mylist)
{
cout << value << endl;
}
``````

}