Describe a method for finding the middle node of a doubly linked list with header and trailer sentinels by link hopping, and without relying on explicit knowledge of the size of the list. In the case of an even number of nodes, report the node slightly left of center as the middle. What is the running time of this method?

Make sure:

Your solution should work on an empty list (return null or throw an exception), as well as lists with > 0 nodes. Give specific pseudocode for this solution. In the case of size=1, you may report that one node as the middle of the list.