382

382. Linked List Random Node (Medium)

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 1:

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.

 

Constraints:

• The number of nodes in the linked list will be in the range [1, 104].
• -104 <= Node.val <= 104
• At most 104 calls will be made to getRandom.

 

Follow up:

• What if the linked list is extremely large and its length is unknown to you?
• Could you solve this efficiently without using extra space?

Companies:
Google, Facebook, Microsoft, Amazon

Related Topics:
Linked List, Math, Reservoir Sampling, Randomized

Similar Questions:

• Random Pick Index (Medium)

Solution 1. Fixed-range Sampling

// OJ: https://leetcode.com/problems/linked-list-random-node/
// Author: github.com/lzl124631x
// Time: O(N) for both
// Space: O(1)
class Solution {
    ListNode *h;
    int len = 0;
public:
    Solution(ListNode* head) : h(head) {
        for (; head; ++len) head = head->next;
    }
    int getRandom() {
        auto p = h;
        for (int k = rand() % len; k-- > 0; p = p->next);
        return p->val;
    }
};

Solution 2. Reservoir Sampling

When we don't know the length, we can use Reservoir Sampling.

When we visit the ith element, we pick it with probability 1 / (i + 1).

For example, when we visit 0th element, we pick it with probablity 1. When we visit the 1th element, we pick it with probability 1/2.

In this way, each element has the same probability of being chosen.

For the 0th element, the probability of being chosen is 1 * 1/2 * 2/3 * 3/4 * ... * (N-1)/N = 1/N.

For the 1th element, the probability of being chosen is 1/2 * 2/3 * 3/4 * ... * (N-1)/N = 1/N.

For the 2th element, the probability of being chosen is 1/3 * 3/4 * ... * (N-1)/N = 1/N.

...

// OJ: https://leetcode.com/problems/linked-list-random-node/
// Author: github.com/lzl124631x
// Time:
//      Solution: O(1)
//      getRandom: O(N)
// Space: O(1)
class Solution {
    ListNode *head;
public:
    Solution(ListNode* head) : head(head) {}
    int getRandom() {
        int base = 1;
        auto p = head, ans = head;
        while (p) {
            int r = rand() % base;
            if (r == 0) ans = p;
            base++;
            p = p->next;
        }
        return ans->val;
    }
};