Reservoir Sampling Solution


  • 0
    Random r;
    ListNode head;
    
    public Solution(ListNode head) {
    	this.r = new Random();
    	this.head = head;
    }
    
    public int getRandom() {
    	int count = 1;
    	ListNode nodeVal = head;
    	ListNode curr = head;
    	while(curr!=null) {
    		if(r.nextInt(count++)==0) nodeVal = curr;
    		curr = curr.next;
    	}
    	return nodeVal.val;
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.