Using reservoir sampling, for each getRandom(), you need to traverse the entire list. Why not just count the length of the list, and then pick the random()%size th node? The average traverse length is just n/2.
What is the benefit of doing reservoir sampling?
Please don't say saving the length takes extra space, because saving the list head also uses space. I don't think O(1) space should be counted as extra space.