Good evening! 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:

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 and 1000000000
• 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

​

import random

import math

​

​

def fetch_random_node(head):

    # fill in

    return head

​

​

# Node definition

class Node:

    def __init__(self, val):

        self.val = val

        self.next = None

​

​

def create_nodes(head, nodes):

    for val in nodes:

        new_node = Node(val)

        head.next = new_node

        head = new_node

​

​

list1 = Node(3)

nodes1 = [4, 5, 6, 7, 8, 9, 10]

create_nodes(list1, nodes1)

​

list2 = Node(1)

nodes2 = [2, 3, 4, 5, 6, 7, 8]

Here's a video of us explaining the solution.

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 our guided, illustrated walk-through.

How do I use this guide?