Leetcode #382. Linked List Random Node

[yokostan]

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    HashMap<Integer, ListNode> map;
    Random rand;

    /** @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) {
        map = new HashMap<>();
        rand = new Random();
        int i = 0;
        while(head != null) {
            map.put(i++, head);
            head = head.next;
        }
    }

    /** Returns a random node's value. */
    public int getRandom() {
        int size = map.size();
        int idx = rand.nextInt(size);
        return map.get(idx).val;
    }
}

/**
 * Your Solution object will be instantiated and called as such:
 * Solution obj = new Solution(head);
 * int param_1 = obj.getRandom();
 */

Using reservoir sampling:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    ListNode h;
    Random rand;

    /** @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) {
        h = head;
        rand = new Random();
    }

    /** Returns a random node's value. */
    public int getRandom() {
        ListNode c = h;
        int r = c.val;
        for (int i = 1; c.next != null; i++) {
            c = c.next;
            if (rand.nextInt(i + 1) == i) r = c.val;
        }
        return r;
    }
}

/**
 * Your Solution object will be instantiated and called as such:
 * Solution obj = new Solution(head);
 * int param_1 = obj.getRandom();
 */