Doubly Linked Lists Question

[jimithing2077]

I have a class assignment and one of the algorithms we are to provide in our Doubly Linked List class is a reverse() function that will reverse the list in O(1) time. Just wondering how exaxctly that can be done?

Obviously O(N) would be simple (reversing each next and prev pointer) but I'm not too sure about doing it in a constant time

Any hints or help would be appreciative

 

[singh]

The key to this problem is that there's really no need to physically "reverse" the list since it is a doubly linked list. You just need to know which "direction" you're going in.

There are a couple of different solutions to this problem, all of which will be O(1) but some will yield a higher O(N) constant during traversal (which your Professor is probably not concerned about).