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 head of the singly-linked list head.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 chosen.
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:
[1, 104].-104 <= Node.val <= 104104 calls will be made to getRandom.
Follow up:
This method involves converting the linked list into an array during the initialization of the Solution object. Once the linked list is stored as an array, we can easily obtain a random node's value by selecting a random index in the array. This guarantees each node has an equal probability of being chosen.
In this solution, we first traverse the linked list to determine its size. We then allocate an array to hold all node values. A second traversal fills the array with the linked list's values. The getRandom function simply selects a random index from the array using the rand() function.
C++
Java
Python
C#
JavaScript
Time Complexity: O(N) for preprocessing, O(1) for getRandom.
Space Complexity: O(N) for storing the list in an array.
Reservoir Sampling is an efficient algorithm that allows you to randomly select a single item from a stream (or a linked list) of unknown length with all items having an equal probability. You can accomplish this by traversing the linked list node by node, replacing the selected item with decreasing probability.
This C solution applies reservoir sampling to randomly select a node from the linked list. For each node, with probability 1/count, the current node value is chosen as the reservoir value, allowing us to accomplish this in one pass with constant space.
C++
Java
Python
C#
JavaScript
Time Complexity: O(N) for getRandom.
Space Complexity: O(1).
| Approach | Complexity |
|---|---|
| Approach 1: Preprocessing with Array | Time Complexity: O(N) for preprocessing, O(1) for |
| Approach 2: Reservoir Sampling | Time Complexity: O(N) for |
Copy List with Random Pointer - Linked List - Leetcode 138 • NeetCode • 159,494 views views
Watch 9 more video solutions →Practice Linked List Random Node with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor