Linked List Random Node

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:

1. Solution(ListNode head) Initializes the object with the head of the singly-linked list head.
2. 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.

Follow up:

1. What if the linked list is extremely large and its length is unknown to you?
2. Could you solve this efficiently without using extra space?

const Solution = function (head) {
  this.indexMap = [];

  let cur = head;
  let curIdx = 0;
  while (cur) {
    this.indexMap[curIdx++] = cur.val;
    cur = cur.next;
  }
};

Solution.prototype.getRandom = function () {
  const rand = Math.floor(Math.random() * this.indexMap.length);
  return this.indexMap[rand];
};

The follow up question with unknown size of linked list would require understanding of Reservoir Sampling.

• this
• this