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.

Translate ยป