Find the fastest duration for a certain distance in a walk
I suggest you use exactly your algorithm, except use binary search during your binary search.  You will want to store the events in an array rather than a linked list, to allow efficient random access into it.  The total running time will be $O(n \log n)$, where $n$ is the number of events in your data structure.  That seems quite reasonable, and this should be quite efficient in practice.