Home » Interview Questions » LinkedList Interview Questions » Can we reverse a linked list in less than O(n) time ?

Can we reverse a linked list in less than O(n) time ?


()

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.

How useful was this post?

Click on a star to rate it!

Average rating / 5. Vote Count

No votes so far! Be the first to rate this post.

As you found this post useful...

Follow us on social media!

We are sorry that this post was not useful for you!

Let us improve this post!

Tell us how we can improve this post?

READ  Add two numbers
Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions