If reference locality is a big concern and k is small, the following might perform better: allocate a ring buffer of size k+1 (ideally on the stack), enqueue the pointers as you go, when you hit the end, return the tail of the buffer.
Among other things, this problem well illustrates how the rules of optimization can vary wildly depending on low level architecture.
That doesn't help significantly, since you only save the final O(k) dereferences. The situation (small k) where it's practical to allocate a ring buffer like this is exactly the situation where it isn't useful.
Actually, you're right, it's the larger values of k where this might make a difference. If the list items are scattered in memory, the cost of the buffer increases very slowly with k compared to the cost of hitting those extra k/2 items.
If reference locality is a big concern and k is small, the following might perform better: allocate a ring buffer of size k+1 (ideally on the stack), enqueue the pointers as you go, when you hit the end, return the tail of the buffer.
Among other things, this problem well illustrates how the rules of optimization can vary wildly depending on low level architecture.