Standard Algorithm R in a special case (k = 1).
from random import randint class Solution(object): def __init__(self, head): """ @param head The linked list's head. Note that the head is guanranteed to be not null, so it contains at least one node. :type head: ListNode """ self.head = head def getRandom(self): """ Returns a random node's value. :rtype: int """ r, node, cnt = self.head.val, self.head.next, 1 while node: cnt += 1 if randint(1,cnt) <= 1: r = node.val node = node.next return r # Your Solution object will be instantiated and called as such: # obj = Solution(head) # param_1 = obj.getRandom()