Good afternoon! Here's our prompt for today.
Given a linked list, can you write a method to get a random node within it? Let's assume you're given a random node generator. The linked list will have at least 2
nodes, and may look something like this:
1 -> 2 -> 3 -> 4
The odds of getting any number between 1
and 4
inclusive should be the exactly the same.

You have access to this definition of a Linked List node:
JAVASCRIPT
1function Node(val) {
2 this.val = val;
3 this.next = null;
4}
Constraints
- Length of the linked list <=
10000
- The nodes will always contain integer values between
-1000000000
and1000000000
- Expected time complexity :
O(n)
- Expected space complexity :
O(n)
Try to solve this here or in Interactive Mode.
How do I practice this challenge?
xxxxxxxxxx
53
'PASSED: ' + 'Checking that we grab a random list node for `list1`'
var assert = require('assert');
​
function fetchRandomNode(headNode) {
// grab random node
return headNode;
}
​
function Node(val) {
this.val = val;
this.next = null;
}
​
function LinkedListNode(val) {
this.val = val;
this.next = null;
}
​
var list1 = new LinkedListNode(3);
var nodes1 = [4, 5, 6, 7, 8, 9, 10];
createNodes(list1, nodes1);
​
var list2 = new LinkedListNode(1);
var nodes2 = [2, 3, 4, 5, 6, 7, 8];
createNodes(list2, nodes2);
​
function createNodes(head, nodes) {
for (let i = 0; i < nodes.length; i++) {
var newNode = new LinkedListNode(nodes[i]);
head.next = newNode;
OUTPUT
:001 > Cmd/Ctrl-Enter to run, Cmd/Ctrl-/ to comment
Tired of reading? Watch this video explanation!
To change the speed of the video or see it in full screen, click the icons to the right of the progress bar.

Here's how we would solve this problem...
How do I use this guide?
Access all course materials today
The rest of this tutorial's contents are only available for premium members. Please explore your options at the link below.