Reservoir Sampling Java Solution


  • 5
    import java.util.Random;
    
    public class Solution {
        ListNode head;
        Random random;
        /** @param head The linked list's head. Note that the head is guanranteed to be not null, so it contains at least one node. */
        public Solution(ListNode head) {
            this.head = head;
            random = new Random();
        }
        
        /** Returns a random node's value. */
        public int getRandom() {
            ListNode result = head;
            ListNode cur = head;
            int size = 1;
            while (cur != null) {
                if (random.nextInt(size) == 0) {
                    result = cur;
                }
                size++;
                cur = cur.next;
            }
            
            return result.val;
        }
    }
    

Log in to reply
 

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