![\"\"](\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1645185692108-Can%20we%20reverse%20a%20linked%20list-08.png\")
<\/p>\n<\/p>\n
Reversing a linked list is a very common operation that we need to perform while solving problems on linked list. So, if this operation is used a lot, let’s look at how fast it can be performed on linked lists of different types. And we will also find the answer to the question: Can we reverse a linked list in less than O(n) time ?<\/p>\n<\/p>\n
To answer this question, let\u2019s discuss this operation on two most commonly used linked lists:<\/p>\n
In a singly linked list, we have the node as:<\/p>\n
struct Node {\n int val;\n Node* next;\n};<\/code><\/pre>\nAnd the singly linked list would look something like:<\/p>\n
![\"\"](\"https:\/\/prepbytes.com\/blog\/wp-content\/uploads\/2021\/08\/Can-we-reverse-a-linked-list-in-less-than-On_1-01.png\")
<\/p>\n
Any method of reversing such a linked list will require at least one traversal of the linked list, visiting each node at least once. Then we can either use extra space or we can simply modify their pointers and reverse them. This can be implemented both recursively and iteratively in linear time. <\/p>\n
So, there seems no way to do this work in less than O(n).<\/p>\n
Doubly linked list<\/h4>\n
A node in a doubly linked list has a pointer to both next and previous nodes.<\/p>\n
struct Node {\n int val;\n Node *next, *prev;\n};<\/code><\/pre>\nAnd the doubly linked list looks something like this:<\/p>\n
![\"\"](\"https:\/\/prepbytes.com\/blog\/wp-content\/uploads\/2021\/08\/Can-we-reverse-a-linked-list-in-less-than-On_2-01.png\")
<\/p>\n
In this doubly-linked list, one thing we can observe is that, if we traverse from the tail pointer towards the node pointed by the head pointer, then we would be traversing the linked list in reverse order.<\/p>\n