Can we write an algorithm to reverse the given linked list in less than O(n) runtime ?
No, we cannot reverse a linked list in O(n) time, because each pointer must be reversed or values must be interchanged to reverse a linked list. To do that we need to reach the last node which takes a pointer to reach last node which takes O(n) time.
It can`t even be done by using recursive and iterative methods.
But you can reverse a memory efficient doubly linked list in O(1) time, it`s just by swapping Tail and Head pointers.
We are sorry that this post was not useful for you!
Let us improve this post!
Tell us how we can improve this post?