382. Linked List Random Node

https://leetcode.com/problems/linked-list-random-node

Python

from random import randint


class Solution:

    def __init__(self, head: Optional[ListNode]):
        n = 0
        cur = head
        while cur:
            n += 1
            cur = cur.next
        self.n = n
        self.head = head

    def getRandom(self) -> int:
        step = randint(0, self.n-1)
        cur = self.head
        for i in range(0, step):
            cur = cur.next

        return cur.val