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.

Implement the Solution class:


	Solution(ListNode head) Initializes the object with the head of the singly-linked list head.
	int getRandom() Chooses a node randomly from the list and returns its value. All the nodes of the list should be equally likely to be chosen.


&nbsp;
Example 1:

Input
["Solution", "getRandom", "getRandom", "getRandom", "getRandom", "getRandom"]
[[[1, 2, 3]], [], [], [], [], []]
Output
[null, 1, 3, 2, 2, 3]

Explanation
Solution solution = new Solution([1, 2, 3]);
solution.getRandom(); // return 1
solution.getRandom(); // return 3
solution.getRandom(); // return 2
solution.getRandom(); // return 2
solution.getRandom(); // return 3
// getRandom() should return either 1, 2, or 3 randomly. Each element should have equal probability of returning.


&nbsp;
Constraints:


	The number of nodes in the linked list will be in the range [1, 104].
	-104 &lt;= Node.val &lt;= 104
	At most 104 calls will be made to getRandom.


&nbsp;
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?


class Solution:

    def __init__(self, head: Optional[ListNode]):
        self.lst = []
        while head:
            self.lst.append(head.val)
            head = head.next

    def getRandom(self) -> int:
        return random.choice(self.lst)
class Solution {
    int N = 0;
    ListNode head = null;
    public Solution(ListNode head) {
        this.head = head;
    }
    
    public int getRandom() {
        ListNode p = this.head;
        int i = 1, ans = 0;
        while (p != null) {
            if (Math.random() * i < 1) ans = p.val; // replace ans with i-th node.val with probability 1/i
            p = p.next;
            i ++;
        }
        return ans;
    }
}
/**
 * Definition for singly-linked list.
 * struct ListNode {
 * int val;
 * ListNode *next;
 * ListNode() : val(0), next(nullptr) {}
 * ListNode(int x) : val(x), next(nullptr) {}
 * ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    vector<int>v;
    Solution(ListNode* head) {
        while(head!=NULL) {
            v.push_back(head->val);
            head=head->next;
        }

    }

    int getRandom() {
        return v[rand()%v.size()];
    }
};

/**
 * Your Solution object will be instantiated and called as such:
 * Solution* obj = new Solution(head);
 * int param_1 = obj->getRandom();
 */
var Solution = function(head) {
        this.res = [];
        let curr = head;

        while(curr !== null) {
            this.res.push(curr)
            curr = curr.next;
        }
        this.length = this.res.length;
};

Solution.prototype.getRandom = function() {
    //Math.random() will generate a random number b/w 0 & 1.
    //then multiply it with the array size, as i have all the value in the list, i know the size of the list
    //take only the integer part which is a random index.
    //return the element at that random index.
    return this.res[Math.floor(Math.random() * this.length)].val
};
Linked List Random Node