Solution For Linked List Random Node

Problem Statement:

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.

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.

Approach:

The given problem can be solved using the reservoir sampling algorithm. The basic idea behind the reservoir sampling algorithm is to select k samples from n elements, where n is either a very large or an unknown number. In this case, n can be the number of nodes in the linked list, and k can be 1 since we want to return a random node’s value.

When the algorithm processes the i-th element in the linked list, it generates a random number between 0 and i (inclusive). If the generated number is 0, the algorithm selects the i-th element as the random sample. Otherwise, the i-th element is included in the sample with a probability of 1/i.

As the algorithm progresses, each element in the linked list has the same probability of being selected as the random sample.

Solution:

We can use the reservoir sampling algorithm to solve the given problem. We can create a helper function to generate a random number between 0 and i (inclusive) and use it to determine whether to update the current random sample in each iteration.

We can maintain two variables:

1. A count variable to keep track of the number of nodes that we have seen so far.
2. A variable to store the value of the current random sample.

In each iteration, we update the count variable and generate a random number between 0 and count (inclusive). If the generated number is 0, we update the random sample variable with the value of the current node’s value.

After we have iterated over all nodes in the linked list, the random sample variable will contain the value of the selected random node.

Code in Python:

“`
class Solution:

def __init__(self, head: ListNode):
    self.head = head

def getRandom(self) -> int:
    count = 0
    curr = self.head
    random_sample = None
    while curr:
        count += 1
        if random.randint(1, count) == 1:
            random_sample = curr.val
        curr = curr.next
    return random_sample

“`

Time Complexity:
The time complexity of the solution is O(N), where N is the number of nodes in the linked list. We iterate through each node in the linked list exactly once.

Space Complexity:
The space complexity of the solution is O(1) since we are only using a few constant amount of extra space for variables.

Step by Step Implementation For Linked List Random Node

/**
 * 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 {
    
    // fields here
    private ListNode head;
    private Random rand;

    /** @param head The linked list's head.
        Note that the head is guaranteed to be not null, so it contains at least one node. */
    public Solution(ListNode head) {
        this.head = head;
        this.rand = new Random();
    }
    
    /** Returns a random node's value. */
    public int getRandom() {
        // Reservoir sampling
        ListNode curr = head;
        int count = 1;
        int res = curr.val;
        while (curr.next != null) {
            curr = curr.next;
            count++;
            if (rand.nextInt(count) == 0) {
                res = curr.val;
            }
        }
        return res;
    }
}

/**
 * Your Solution object will be instantiated and called as such:
 * Solution obj = new Solution(head);
 * int param_1 = obj.getRandom();
 */

# 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: ListNode):
        """
        @param head The linked list's head.
        Note that the head is guaranteed to be not null, so it contains at least one node.
        """
        self.head = head
        

    def getRandom(self) -> int:
        """
        Returns a random node's value.
        """
        curr = self.head
        count = 1
        res = curr.val
        while curr.next:
            curr = curr.next
            count += 1
            if random.randint(1, count) == 1:
                res = curr.val
        return res

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param head The linked list's head.
        Note that the head is guaranteed to be not null, so it contains at least one node.
 * @param {ListNode} head
 */
var Solution = function(head) {
    this.head = head;
};

/**
 * Returns a random node's value.
 * @return {number}
 */
Solution.prototype.getRandom = function() {
    // create a copy of the head
    let curr = this.head;
    // create a variable to store the length of the list
    let len = 0;
    // create a variable to store the result
    let result = null;
    // iterate through the list to get the length
    while (curr) {
        len++;
        curr = curr.next;
    }
    // reset curr back to head
    curr = this.head;
    // use a for loop to iterate through the list again
    // inside the loop, generate a random number between 1 and len
    // if the random number is equal to 1, store the current value in result
    for (let i = 1; i <= len; i++) {
        let rand = Math.ceil(Math.random() * len);
        if (rand === 1) {
            result = curr.val;
        }
        curr = curr.next;
    }
    // return the result
    return result;
};

/**
 * 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:
    /** @param head The linked list's head.
        Note that the head is guaranteed to be not null, so it contains at least one node. */
    Solution(ListNode* head) {
        
    }
    
    /** Returns a random node's value. */
    int getRandom() {
        
    }
};

/**
 * Your Solution object will be instantiated and called as such:
 * Solution* obj = new Solution(head);
 * int param_1 = obj->getRandom();
 */

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int val=0, ListNode next=null) {
 *         this.val = val;
 *         this.next = next;
 *     }
 * }
 */
public class Solution {

    ListNode head;
    Random random;
    
    /** @param head The linked list's head.
        Note that the head is guaranteed to be not null, so it contains at least one node. */
    public Solution(ListNode head) {
        this.head = head;
        this.random = new Random();
    }
    
    /** Returns a random node's value. */
    public int GetRandom() {
        ListNode curr = head;
        int count = 1;
        int result = curr.val;
        
        //use reservoir sampling to get a random node from the linked list
        while (curr.next != null){
            curr = curr.next;
            count++;
            if (random.nextInt(count) == 0){
                result = curr.val;
            }
        }
        
        return result;
    }
}

/**
 * Your Solution object will be instantiated and called as such:
 * Solution obj = new Solution(head);
 * int param_1 = obj.GetRandom();
 */