🎨Now live: Try our Free AI Image Generation Feature

Description
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.
Intuition
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.
Approach
- Initialization: - Traverse the entire linked list once and store the nodes in a list or array. - This allows constant-time random access to any node.
- Random Selection:
- When the
getRandom()
function is called, generate a random index within the bounds of the array. - Return the node's value at this randomly chosen index. - Efficiency: - Storing all nodes in an array requires only a single traversal of the list. - Accessing any node is then reduced to O(1) time using random indexing.
- Edge Cases: - If the list is empty (though it's usually assumed that the list has at least one node), we should handle such cases in real-world scenarios.
Complexity
Time Complexity:
- Initialization: O(n), where n is the number of nodes in the linked list.
- Random Selection: O(1), as accessing an array element by index is a constant-time operation.
Space Complexity:
O(n), where n is the number of nodes, since we store all the nodes in an array.
Code
C++
class Solution {
public:
vector 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;
}
};
Python
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
Java
class Solution {
private ArrayList 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;
}
}
JavaScript
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
};