Welcome to Subscribe On Youtube

382. Linked List Random Node

Description

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

Solutions

  • /**
     * 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();
     */
    
  • /**
     * 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();
     */
    
  • # 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()
    
    
    
  • /**
     * Definition for singly-linked list.
     * type ListNode struct {
     *     Val int
     *     Next *ListNode
     * }
     */
    type Solution struct {
    	head *ListNode
    }
    
    func Constructor(head *ListNode) Solution {
    	return Solution{head}
    }
    
    func (this *Solution) GetRandom() int {
    	n, ans := 0, 0
    	for node := this.head; node != nil; node = node.Next {
    		n++
    		x := 1 + rand.Intn(n)
    		if n == x {
    			ans = node.Val
    		}
    	}
    	return ans
    }
    
    /**
     * Your Solution object will be instantiated and called as such:
     * obj := Constructor(head);
     * param_1 := obj.GetRandom();
     */
    

All Problems

All Solutions