The problem is about selecting a random node from a singly linked list. Since the list's length is unknown initially, the challenge is to find an efficient way to retrieve random nodes. The solution should ensure that each node has an equal probability of being chosen.
The simplest way to randomly access nodes in a linked list is to first convert the list into an array (or any other data structure with constant-time access). Once stored in this manner, selecting a random element becomes trivial. This approach avoids the need to traverse the list multiple times while providing efficient random access.
Initialization:
Random Selection:
getRandom()
function is called, generate a random index within the bounds of the array.Efficiency:
Edge Cases:
O(n), where n is the number of nodes, since we store all the nodes in an array.
class Solution {
public:
vector<ListNode*> res;
int length;
Solution(ListNode* head) {
ListNode* curr = head;
while (curr != nullptr) {
res.push_back(curr);
curr = curr->next;
}
length = res.size();
}
int getRandom() {
int index = rand() % length;
return res[index]->val;
}
};
class Solution:
def __init__(self, head: ListNode):
self.res = []
curr = head
while curr:
self.res.append(curr)
curr = curr.next
self.length = len(self.res)
def getRandom(self) -> int:
index = random.randint(0, self.length - 1)
return self.res[index].val
class Solution {
private ArrayList<ListNode> res;
private int length;
private Random random;
public Solution(ListNode head) {
res = new ArrayList<>();
ListNode curr = head;
while (curr != null) {
res.add(curr);
curr = curr.next;
}
length = res.size();
random = new Random();
}
public int getRandom() {
int index = random.nextInt(length);
return res.get(index).val;
}
}
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 () {
return this.res[Math.floor(Math.random() * this.length)].val
};