Today's Puzzle, brought to you by Google and Palantir:

You are given a pointer to the first element of a linked list of unknown length N.
Write an algorithm that in O(N) time and O(1) space picks a random element from the
list where each element has the same probability of being chosen.  You also only get
one pass over the list.

Now, generalize your algorithm.  Suppose that I give you the same setup as before and
a number k.  Write an algorithm that picks k elements from the list with uniform
probability in O(N) time, one pass over the array, and O(k) space.