I realized that this is very similar to the problem to picking a random number from a stream. For both problems, you don't know what the length of the linked list or the stream and it can be solved with constant memory.

The algorithm is as follows:

Iterate through all the nodes in the linked list while keep track of the index of the node in base 1. So the first node with have a number of 1, the second will have a number of 2.

For every node, let there be a probability of 1/(base 1 index of node) of it being picked.

```
public class Solution {
/** @param head The linked list's head.
Note that the head is guaranteed to be not null, so it contains at least one node. */
ListNode head;
Random rand;
public Solution(ListNode head) {
this.head = head;
rand = new Random();
}
/** Returns a random node's value. */
public int getRandom() {
ListNode result = null;
ListNode cand = this.head;
int count = 1;
while(cand != null) {
if(shouldBePicked(count)) {
result = cand;
}
cand = cand.next;
count++;
}
return result.val;
}
public boolean shouldBePicked(int denom) {
int value = this.rand.nextInt(denom);
return value == 0;
}
}
```