# Linked List Random Node
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/linked-list-random-node)
Canonical: https://scaleengineer.com/dsa/problems/linked-list-random-node
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Randomized](https://scaleengineer.com/dsa/patterns/randomized)
**Algorithms:** [Reservoir Sampling](https://scaleengineer.com/algorithms/reservoir-sampling)
**Data structures:** Linked List
**Companies:** [Nvidia](https://scaleengineer.com/companies/nvidia)
---
## 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 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:**

![](https://assets.glich.co/dsa/linked-list-random-node/image0.jpg) 

**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?

# Approaches
## Convert to Array and Pick Random
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.
**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`.
**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.
### Explanation
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.

```java
import java.util.ArrayList;
import java.util.List;
import java.util.Random;

/**
 * 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 List<Integer> values;
    private Random rand;

    public Solution(ListNode head) {
        this.values = new ArrayList<>();
        this.rand = new Random();
        ListNode curr = head;
        while (curr != null) {
            this.values.add(curr.val);
            curr = curr.next;
        }
    }
    
    public int getRandom() {
        int randomIndex = rand.nextInt(this.values.size());
        return this.values.get(randomIndex);
    }
}
```
### 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)`.

## Two-Pass Traversal
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.
**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()`.
**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.
### Explanation
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.

```java
import java.util.Random;

/**
 * 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 rand;

    public Solution(ListNode head) {
        this.head = head;
        this.rand = new Random();
    }
    
    public int getRandom() {
        int length = 0;
        ListNode curr = head;
        while (curr != null) {
            length++;
            curr = curr.next;
        }
        
        int randomIndex = rand.nextInt(length);
        
        curr = head;
        for (int i = 0; i < randomIndex; i++) {
            curr = curr.next;
        }
        return curr.val;
    }
}
```
### 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.

## Reservoir Sampling (Single Pass)
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.
**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.
**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.
### Explanation
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.

```java
import java.util.Random;

/**
 * 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 rand;

    public Solution(ListNode head) {
        this.head = head;
        this.rand = new Random();
    }
    
    public int getRandom() {
        int scope = 1;
        int chosenValue = 0;
        ListNode curr = this.head;
        while (curr != null) {
            // Decide whether to replace the chosen value with the current node's value.
            // The probability of rand.nextInt(scope) == 0 is 1/scope.
            if (rand.nextInt(scope) == 0) {
                chosenValue = curr.val;
            }
            scope++;
            curr = curr.next;
        }
        return chosenValue;
    }
}
```
### 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`.

# Solutions
### Java

```java
/** * 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(); */
```

### CPP

```cpp
/** * 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(); */
```

### Python

```python
# 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()
```