Medium

Quiz

#382 Linked List Random Node

APPROACH

Build a structure around a singly linked list that can return a uniformly random node value on demand, with every node equally likely to be selected.

Implement the Solution class:

- Solution(ListNode head) Wraps the linked list starting at head.

- int getRandom() Picks a node at random and returns its value, each node equally likely.

Example 1:

Input

["Solution", "getRandom", "getRandom", "getRandom", "getRandom", "getRandom"]

[[[1, 2, 3]], [], [], [], [], []]

Output

[null, 1, 3, 2, 2, 3]

Example 2:

Explanation

Solution solution = new Solution([1, 2, 3]);

solution.getRandom(); // return 1

solution.getRandom(); // return 3

solution.getRandom(); // return 2

solution.getRandom(); // return 3

// getRandom() should return either 1, 2, or 3 randomly. Each element should have equal probability of returning.

1 of 4

1:00

What is the optimal approach for this problem?