1 class Solution(object):
 2 
 3     def __init__(self, head):
 4         """
 5         @param head The linked list‘s head.
 6         Note that the head is guaranteed to be not null, so it contains at least one node.
 7         :type head: ListNode
 8         """
 9         self.head = head
10 
11     def getRandom(self):
12         """
13         Returns a random node‘s value.
14         :rtype: int
15         """
16         cnt = 0
17         head = self.head
18         while head:
19             if random.randint(0, cnt) == 0:
20                 ans = head.val
21             head = head.next
22             cnt += 1
23         return ans