reservior sampling

class Solution:

    def __init__(self, head: ListNode):
        """
        @param head The linked list's head.
        Note that the head is guaranteed to be not null, so it contains at least one node.
        """

        self.head = head


    def getRandom(self) -> int:
        """
        Returns a random node's value.
        """

        res = -1
        counter = 0

        head = self.head


        while(head):
            counter += 1
            if counter == 1:
                res = head.val
            else:
                rand = randint(1, counter)
                if rand == 1:
                    res = head.val

            head = head.next

        return res