[LeetCode] Linked List Random Node

Problem: Given a singly linked list, return a random node's value from the linked list. Each node must have the same probability of being chosen.

Implement the Solution class:

• Solution(ListNode head) Initializes the object with the integer array nums.
• int getRandom() Chooses a node randomly from the list and returns its value. All the nodes of the list should be equally likely to be choosen.

Example:

Input
["Solution", "getRandom", "getRandom", "getRandom", "getRandom", "getRandom"]
[[[1, 2, 3]], [], [], [], [], []]
Output
[null, 1, 3, 2, 2, 3]

Explanation
Solution solution = new Solution([1, 2, 3]);
solution.getRandom(); // return 1
solution.getRandom(); // return 3
solution.getRandom(); // return 2
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.

Approach: We can take a private member of type List and just put all the values of the input Linked List into it. Now whenever we will get a call of getRandom(), we can generate a random index and return the value at that index in that list. That's all!

Note that here we are assuming the list size is not getting changed very frequently. If it is the case then we just can't rely on this approach and we need to use Reservoir Sampling.

Implementation in C#:

public class Solution 

{

    public Solution(ListNode head) 

    {

        this.listValues = new List<int>();

        ListNode itr = head;

        while (itr != null)

        {

            this.listValues.Add(itr.val);

            itr = itr.next;

        }

    }

    

    public int GetRandom() {

        int index = new Random().Next() % this.listValues.Count;

        return this.listValues[index];

    }

    

    private List<int> listValues;

}

Complexity: O(n) for constructor and O(1) for getRandom()