Comment by School-Cotton

Presumably the list is not ordered adversarially, so you can just use quickselect, at O(n) running time.