Given a singly linked list, return a random node's value from the linked list. Each node must have the same probability of being chosen.

Follow up:
What if the linked list is extremely large and its length is unknown to you? Could you solve this efficiently without using extra space?

Example:

// Init a singly linked list [1,2,3].
ListNode head = new ListNode(1);
head.next = new ListNode(2);
head.next.next = new ListNode(3);
Solution solution = new Solution(head);

// getRandom() should return either 1, 2, or 3 randomly. Each element should have equal probability of returning.
solution.getRandom();

1. from head move down random steps, if hit the end, put the end back to head. 
**The problem with this is that with the first getRandom call, it will never select anything beyond the random range set at the beginning. the randomism will only achieve after infinite calls.

2. find the length of the list, l. find a random number between 0 and l-1, say k. go down k steps.
**Problem: need to scan the list twice at worst case.

3. if list len is 1. the chance of select n1 is 1. if 1 has next, say 2, and 2 stop, the chance of selecting 2 is 1/2. if it stops at 3, the chance of chance of selecting 3 is 1/3... then 1/4, 1/5, 1/6 ... for the ith number to be chosen, the chance is 1/i. So need a i counter to keep the denominator grow till we find the len of the list. **We cannot know the real pobability of selecting any number unless we know the size of the sample pool.

**********398ms
# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    from random import *

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

    def getRandom(self):
        """
        Returns a random node's value.
        :rtype: int
        """
        i = 1
        r = self.r
        res = r.val
        while r.next:
            i += 1
            ran = random.randint(1,i)
            r = r.next
            if ran == 1:
                res = r.val
        return res
            

# Your Solution object will be instantiated and called as such:
# obj = Solution(head)
# param_1 = obj.getRandom()

from other ppl's solution:

1. Why this is much faster?? 256ms:
import random
class Solution(object):

    def __init__(self, head):
        """
        @param head The linked list's head.
        Note that the head is guaranteed 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
        """
        c = self.head
        r = self.head.val
        i = 1
        while c and c.next:
            c = c.next
            if random.randrange(i + 1) == i:
                r = c.val
            i += 1
        return r
		
2. use random instead of randint, 165ms:
def getRandom(self):
	"""
	Returns a random node's value.
	:rtype: int
	"""
	t = None
	c = 0
	h = self.head
	while h:
		c += 1
		x = random.random()
		if x <= 1.0 / c:
			t = h
		h = h.next
	return t.val
	
3. sneaky sneaky. put the array in the constructor, lots of mem but 112ms:
# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None
import random
class Solution(object):

    def __init__(self, head):
        """
        @param head The linked list's head.
        Note that the head is guaranteed to be not null, so it contains at least one node.
        :type head: ListNode
        """
        self.vals = []
        cur = head
        while cur!=None:
            self.vals.append(cur.val)
            cur = cur.next
        self.l = len(self.vals)

    def getRandom(self):
        """
        Returns a random node's value.
        :rtype: int
        """
        return self.vals[random.randint(0,self.l-1)]