Given a sorted, doubly linked list, how would you go about finding the median element? The one way I can think of is to traverse the list once and once a value repeats, We know we've traversed the whole linked list. At his point, we know how many elements there are, so we can go the median since it's already sorted, which would be:

running time: O(n)
space complexity O(n) as well. 

Is there a more efficient way of doing this?