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();

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param head The linked list's head.
        Note that the head is guaranteed to be not null, so it contains at least one node.
 * @param {ListNode} head
 */
var Solution = function(head) {
    this.head = head;
};

/**
 * Returns a random node's value.
 * @return {number}
 */
Solution.prototype.getRandom = function() {
    
    var total = 1;
    var p = this.head;
    while(p.next !== null){
        p = p.next;
        total++;
    }
    
    var index =  Math.floor(Math.random() * Math.floor(total))
    var p = this.head;
    for(var i=0;i<index;i++){
        p = p.next;
    }
    
    return p.val;
    
};

/** 
 * Your Solution object will be instantiated and called as such:
 * var obj = new Solution(head)
 * var param_1 = obj.getRandom()
 */

Random Set- Phone Interview
CompletedJune 1, 2019 7:41 AM
Time Spent: 38 minutes 29 seconds
Time Allotted: 1 hour 30 minutes
In order to provide you a more accurate assessment, we are waiting for more users to take this interview.
Email me when my report is ready
Find Pivot Index
EASY
741 / 741 Testcases Passed
Details
Linked List Random Node
MEDIUM
7 / 7 Testcases Passed