Java Solution with Reservoir sampling, O(1) space O(n) time


  • 1
    S

    ...
    import java.util.Random;
    public class Solution {
    ListNode 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. */
    public Solution(ListNode head) {
        this.head = head;
    }
    
    /** Returns a random node's value. */
    public int getRandom() {
        int res = head.val;
        ListNode p = head.next;
        int len = 1;
        Random rm = new Random();
        int ran = 0;
        while (p != null) {
            ran = rm.nextInt(++len);
            if (ran == 0) {
                res = p.val;
            }
            p = p.next;
        }
        return res;
    }
    

    }
    ...


Log in to reply
 

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