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;
tail = head;
head = temp;
}
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 
Here’s the answer to your query :
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.
Answer is Yes.
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
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>
class DoubleLinkedList
{
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:
friend class DoubleLinkedList;
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;
DoubleLinkedList& m_containingList;
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()
{
DoubleLinkedList<int> mylist;
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 answer is Yes.
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
class DoubleLinkedList
{
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:
friend class DoubleLinkedList;
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;
DoubleLinkedList& m_containingList;
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()
{
DoubleLinkedList mylist;
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;
}
}