# 382-linked-list-random-node


Try it on <a href='https://leetcode.com/problems/382-linked-list-random-node'>leetcode</a>

## Description
<div class="description">
<div><p>Given a singly linked list, return a random node's value from the linked list. Each node must have the <strong>same probability</strong> of being chosen.</p>

<p>Implement the <code>Solution</code> class:</p>

<ul>
	<li><code>Solution(ListNode head)</code> Initializes the object with the integer array nums.</li>
	<li><code>int getRandom()</code> Chooses a node randomly from the list and returns its value. All the nodes of the list should be equally likely to be choosen.</li>
</ul>

<p>&nbsp;</p>
<p><strong>Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/03/16/getrand-linked-list.jpg" style="width: 302px; height: 62px;">
<pre><strong>Input</strong>
["Solution", "getRandom", "getRandom", "getRandom", "getRandom", "getRandom"]
[[[1, 2, 3]], [], [], [], [], []]
<strong>Output</strong>
[null, 1, 3, 2, 2, 3]

<strong>Explanation</strong>
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.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li>The number of nodes in the linked list will be in the range <code>[1, 10<sup>4</sup>]</code>.</li>
	<li><code>-10<sup>4</sup> &lt;= Node.val &lt;= 10<sup>4</sup></code></li>
	<li>At most <code>10<sup>4</sup></code> calls will be made to <code>getRandom</code>.</li>
</ul>

<p>&nbsp;</p>
<p><strong>Follow up:</strong></p>

<ul>
	<li>What if the linked list is extremely large and its length is unknown to you?</li>
	<li>Could you solve this efficiently without using extra space?</li>
</ul>
</div>
</div>

## Solution(Python)
```Python
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    # @Problem Statement:
    #   Given a Singly LinkedList return a RandomNode
    #
    # @Input: Head Node
    # @Output: Random Node
    #
    # @sample Input:
    #   1.[1,2,3] get Random -> 3 ,2,1,1,2,3
    #       All of them with equal probabaility
    #
    # @constraints:
    #   * N = [1,10^4]
    #   * -10^4 <= N.val <= 10^4
    #   * Atmost 10^4 calls
    #
    # @Solutions:
    #   1. Using array of node values:
    #       Idea:
    #           * init() -> stores linkedList in a array
    #           * getrandom -> return random sample from array
    #
    #       Complexity Analysis:
    #           * Time Complexity:init() -> O(n)
    #                           getrandom() -> O(1)
    #           * Space Complexity: O(n)
    #       code:
    #          def __init__(self, head: Optional[ListNode]):
    #               self.arr = []
    #
    #               while head:
    #                   self.arr.append(head.val)
    #                   head = head.next
    #               self.n = len(self.arr)
    #
    #           def getRandom(self) -> int:
    #               randIn = int(random.random()*self.n)
    #
    #               return self.arr[randIn]
    #   --------------------------------------------------
    #  2.By Maintaing Reservior Array:
    #       At Start We store the Reservior array of size k
    #       with elements from the input
    #       To ensure equal probability of picking elements from the array
    #       i.e k/n for all elements we should pick random values within
    #       k  for values outside k  we can discard it
    #
    #       Complexity Analysis:
    #           * Time Complexity:init() -> O(1)
    #                           getrandom() -> O(n)
    #           * Space Complexity: O(1)
    def __init__(self, head: Optional[ListNode]):
        self.headNode = head

    def getRandom(self) -> int:
        k = 1
        chosen_val = 0
        cur = self.headNode

        while cur:
            if random.random() < 1 / k:
                chosen_val = cur.val
            cur = cur.next
            k += 1
        return chosen_val


# Your Solution object will be instantiated and called as such:
# obj = Solution(head)
# param_1 = obj.getRandom()

```