Linked List Random Node

Med

#0369Time: Constructor: O(N) to traverse the list and build the `ArrayList`. `getRandom()`: O(1) for random index generation and access.Space: O(N), where N is the number of nodes in the linked list. This is because we need to store all the node values in an auxiliary `ArrayList`.1 company

Patterns

Algorithms

Data structures

Companies

Prompt

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:

The number of nodes in the linked list will be in the range [1, 10⁴].
-10⁴ <= Node.val <= 10⁴
At most 10⁴ 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?

Approaches

3 approaches with complexity analysis and trade-offs.

This approach involves pre-processing the linked list by converting it into a data structure that allows for constant-time random access, such as an ArrayList. During initialization, we traverse the entire linked list and store each node's value in an ArrayList. This makes subsequent calls to getRandom very fast.

Algorithm

In the constructor:
1. Initialize an empty ArrayList, say values.
2. Initialize a Random object.
3. Iterate through the linked list starting from the head.
4. For each node encountered, add its value to the values list.
In the getRandom() method:
1. Get the size of the values list, let's call it n.
2. Generate a random integer idx in the range [0, n-1].
3. Return the element at values.get(idx).

Walkthrough

The Solution constructor is responsible for the conversion. It initializes an ArrayList and iterates through the linked list from the head, adding each node's value to this list. The ArrayList is then stored as a member variable.

The getRandom method leverages this pre-processed list. It simply gets the size of the stored ArrayList, generates a random integer index in the range [0, size-1], and returns the element at that index using get(). This operation is very fast and ensures that each element has an equal 1/size probability of being chosen.

1import java.util.ArrayList;2import java.util.List;3import java.util.Random;4 5/**6 * Definition for singly-linked list.7 * public class ListNode {8 *     int val;9 *     ListNode next;10 *     ListNode() {}11 *     ListNode(int val) { this.val = val; }12 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }13 * }14 */15class Solution {16    private List<Integer> values;17    private Random rand;18 19    public Solution(ListNode head) {20        this.values = new ArrayList<>();21        this.rand = new Random();22        ListNode curr = head;23        while (curr != null) {24            this.values.add(curr.val);25            curr = curr.next;26        }27    }28    29    public int getRandom() {30        int randomIndex = rand.nextInt(this.values.size());31        return this.values.get(randomIndex);32    }33}

Complexity

Time

Constructor: O(N) to traverse the list and build the `ArrayList`. `getRandom()`: O(1) for random index generation and access.

Space

O(N), where N is the number of nodes in the linked list. This is because we need to store all the node values in an auxiliary `ArrayList`.

Trade-offs

Pros

The getRandom() method is extremely fast, with a time complexity of O(1).
The implementation is straightforward and easy to understand.

Cons

Requires O(N) extra space, which can be prohibitive for very large linked lists.
Does not satisfy the follow-up question about solving the problem efficiently without extra space.
The initial setup in the constructor takes O(N) time, which might be a bottleneck if the object is created frequently.

This approach avoids using extra space proportional to the list's size by performing the work within the getRandom method. Each call to getRandom involves two traversals of the list. The first pass is to determine the length of the list, and the second pass is to find the randomly selected node.

Algorithm

In the constructor:
1. Store the head of the linked list.
2. Initialize a Random object.
In the getRandom() method:
1. First Pass: Initialize a counter length = 0. Traverse the list from the head to the end, incrementing length for each node to find the total number of nodes.
2. Random Selection: Generate a random index randomIndex from 0 to length - 1.
3. Second Pass: Start another traversal from the head. Move randomIndex steps forward to reach the target node.
4. Return the value of the target node.

Walkthrough

The constructor's role is minimal; it simply stores a reference to the head of the list. All the logic is contained within the getRandom method.

When getRandom is called, it first performs a full traversal to count the total number of nodes, N. With the length known, it generates a random integer k in the range [0, N-1]. To find the node corresponding to this index, it must traverse the list a second time from the beginning, stopping after k steps. The value of the node at this position is then returned. While this method successfully uses constant space, the time complexity for each random selection is linear.

1import java.util.Random;2 3/**4 * Definition for singly-linked list.5 * public class ListNode {6 *     int val;7 *     ListNode next;8 *     ListNode() {}9 *     ListNode(int val) { this.val = val; }10 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }11 * }12 */13class Solution {14    private ListNode head;15    private Random rand;16 17    public Solution(ListNode head) {18        this.head = head;19        this.rand = new Random();20    }21    22    public int getRandom() {23        int length = 0;24        ListNode curr = head;25        while (curr != null) {26            length++;27            curr = curr.next;28        }29        30        int randomIndex = rand.nextInt(length);31        32        curr = head;33        for (int i = 0; i < randomIndex; i++) {34            curr = curr.next;35        }36        return curr.val;37    }38}

Complexity

Time

Constructor: O(1). `getRandom()`: O(N) because it requires traversing the list twice (once to find the length, and once to find the element).

Space

O(1), as we only store the head pointer and a few temporary variables during the execution of `getRandom()`.

Trade-offs

Pros

It is very space-efficient, using only O(1) extra space.
It satisfies the follow-up constraint of not using extra space.

Cons

The getRandom() method is inefficient, with a time complexity of O(N).
Each call to getRandom() requires two full traversals of the list in the worst case, which is slower than a single-pass solution.

This is an optimal approach that solves the problem in a single pass with constant extra space. It uses a technique called Reservoir Sampling. This algorithm is particularly well-suited for selecting a random sample from a population of unknown size, which is analogous to our linked list whose length we might not know beforehand.

Algorithm

In the constructor:
1. Store the head of the linked list.
2. Initialize a Random object.
In the getRandom() method:
1. Initialize a variable chosenValue to store the result and a counter scope = 1.
2. Start a traversal from the head node, let's call it current.
3. For each node current: a. Generate a random integer from 0 to scope - 1. b. If the random integer is 0 (this happens with probability 1/scope), update chosenValue with current.val. c. Move to the next node (current = current.next) and increment scope.
4. After the loop finishes, return chosenValue.

Walkthrough

The core idea is to iterate through the list and, at each node, decide whether to replace our current random choice with the new node. For the i-th node we encounter, we choose it to be the new candidate with a probability of 1/i. This ensures that after iterating through all N nodes, every node has had an equal 1/N probability of being the final chosen node.

Specifically, we traverse the list, keeping track of the number of nodes seen so far (scope). For each node, we generate a random number. If this random number meets a specific condition (e.g., it's 0 for a random range of [0, scope-1]), we update our result with the current node's value. This method elegantly handles the requirements without knowing the list's length in advance and uses only constant extra space.

1import java.util.Random;2 3/**4 * Definition for singly-linked list.5 * public class ListNode {6 *     int val;7 *     ListNode next;8 *     ListNode() {}9 *     ListNode(int val) { this.val = val; }10 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }11 * }12 */13class Solution {14    private ListNode head;15    private Random rand;16 17    public Solution(ListNode head) {18        this.head = head;19        this.rand = new Random();20    }21    22    public int getRandom() {23        int scope = 1;24        int chosenValue = 0;25        ListNode curr = this.head;26        while (curr != null) {27            // Decide whether to replace the chosen value with the current node's value.28            // The probability of rand.nextInt(scope) == 0 is 1/scope.29            if (rand.nextInt(scope) == 0) {30                chosenValue = curr.val;31            }32            scope++;33            curr = curr.next;34        }35        return chosenValue;36    }37}

Complexity

Time

Constructor: O(1). `getRandom()`: O(N), as it requires one full traversal of the list for each call.

Space

O(1). We only use a few variables to store the head, the result, and the current scope.

Trade-offs

Pros

Extremely space-efficient, using O(1) extra space.
Solves the problem in a single pass per getRandom() call.
Perfectly addresses the follow-up questions, as it works for lists of unknown size and without using extra space.

Cons

getRandom() still takes linear time, O(N), which might be slow if it's called very frequently on a very large list.

Solutions

Solution

1/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { private ListNode head ; private Random random = new Random (); public Solution ( ListNode head ) { this . head = head ; } public int getRandom () { int ans = 0 , n = 0 ; for ( ListNode node = head ; node != null ; node = node . next ) { ++ n ; int x = 1 + random . nextInt ( n ); if ( n == x ) { ans = node . val ; } } return ans ; } } /** * Your Solution object will be instantiated and called as such: * Solution obj = new Solution(head); * int param_1 = obj.getRandom(); */

1/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: ListNode * head ; Solution ( ListNode * head ) { this -> head = head ; } int getRandom () { int n = 0 , ans = 0 ; for ( ListNode * node = head ; node != nullptr ; node = node -> next ) { n += 1 ; int x = 1 + rand () % n ; if ( n == x ) ans = node -> val ; } return ans ; } }; /** * Your Solution object will be instantiated and called as such: * Solution* obj = new Solution(head); * int param_1 = obj->getRandom(); */

1# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution : def __init__ ( self , head : Optional [ ListNode ]): self . head = head def getRandom ( self ) -> int : n = ans = 0 head = self . head while head : n += 1 x = random . randint ( 1 , n ) if n == x : ans = head . val head = head . next return ans # Your Solution object will be instantiated and called as such: # obj = Solution(head) # param_1 = obj.getRandom() ############ # Definition for singly-linked list. # class ListNode(object): # def __init__(self, x): # self.val = x # self.next = None import random class Solution ( object ): def __init__ ( self , head ): """ @param head The linked list's head. Note that the head is guaranteed to be not null, so it contains at least one node. :type head: ListNode """ self . head = head def getRandom ( self ): """ Returns a random node's value. :rtype: int """ ans = self . head . val head = self . head idx = 1 while head : if random . randrange ( 1 , idx + 1 ) == idx : ans = head . val head = head . next idx += 1 return ans # Your Solution object will be instantiated and called as such: # obj = Solution(head) # param_1 = obj.getRandom()

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem

Solution

1/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { private ListNode head ; private Random random = new Random (); public Solution ( ListNode head ) { this . head = head ; } public int getRandom () { int ans = 0 , n = 0 ; for ( ListNode node = head ; node != null ; node = node . next ) { ++ n ; int x = 1 + random . nextInt ( n ); if ( n == x ) { ans = node . val ; } } return ans ; } } /** * Your Solution object will be instantiated and called as such: * Solution obj = new Solution(head); * int param_1 = obj.getRandom(); */

1/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: ListNode * head ; Solution ( ListNode * head ) { this -> head = head ; } int getRandom () { int n = 0 , ans = 0 ; for ( ListNode * node = head ; node != nullptr ; node = node -> next ) { n += 1 ; int x = 1 + rand () % n ; if ( n == x ) ans = node -> val ; } return ans ; } }; /** * Your Solution object will be instantiated and called as such: * Solution* obj = new Solution(head); * int param_1 = obj->getRandom(); */

1# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution : def __init__ ( self , head : Optional [ ListNode ]): self . head = head def getRandom ( self ) -> int : n = ans = 0 head = self . head while head : n += 1 x = random . randint ( 1 , n ) if n == x : ans = head . val head = head . next return ans # Your Solution object will be instantiated and called as such: # obj = Solution(head) # param_1 = obj.getRandom() ############ # Definition for singly-linked list. # class ListNode(object): # def __init__(self, x): # self.val = x # self.next = None import random class Solution ( object ): def __init__ ( self , head ): """ @param head The linked list's head. Note that the head is guaranteed to be not null, so it contains at least one node. :type head: ListNode """ self . head = head def getRandom ( self ): """ Returns a random node's value. :rtype: int """ ans = self . head . val head = self . head idx = 1 while head : if random . randrange ( 1 , idx + 1 ) == idx : ans = head . val head = head . next idx += 1 return ans # Your Solution object will be instantiated and called as such: # obj = Solution(head) # param_1 = obj.getRandom()

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.