Random node of a linked list

You get the head of a singly linked list of ListNode(val, next) nodes. Implement:

• Solution(head, rng): rng is a random.Random. Use it for every random choice (e.g. rng.randrange(k)), never the global random module, so the tests can seed it.
• get_random() -> int: the value of a node chosen uniformly at random. Every node must be equally likely (so a value that appears twice is twice as likely).

The catch: treat the list as a stream of unknown length. Nodes may be appended to the tail between calls, so don't copy the list into an array or cache its length in the constructor. Walk it on each call, in one pass, using O(1) extra space.

head = ListNode(10, ListNode(20, ListNode(30)))
s = Solution(head, random.Random(0))
s.get_random()   # 10, 20 or 30, each with probability 1/3
head.next.next.next = ListNode(40)
s.get_random()   # now 10, 20, 30 or 40, each with probability 1/4

Constraints: 1 ≤ list length ≤ 10^4.