382. Linked List Random Node

// LeetCode URL: https://leetcode.com/problems/linked-list-random-node/
import java.util.Random;

//   Definition for singly-linked list.
class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
    }
}

/**
 * Reservoir Sampling
 *
 * Suppose there are 1 to N numbers in the list. You have already picked i-1
 * elements. Now you are trying to pick ith element. The probability to pick it
 * is 1/i. Now you do not want to pick any future numbers.. Thus, the final
 * probability for ith element = 1/i * (1 - 1/(i+1)) * (1 - 1/(i+2)) * .. * (1 -
 * 1/N) = 1 / N.
 *
 * Time Complexity: 1) Solution() -> O(1).. 2) pick() -> O(N)
 *
 * Space Complexity: O(1)
 *
 * N = Length of the input array.
 */
class Solution {

    ListNode listHead;
    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) {
        if (head == null) {
            return;
        }
        listHead = head;
        rand = new Random();
    }

    /** Returns a random node's value. */
    public int getRandom() {
        if (listHead == null) {
            return -1;
        }

        ListNode cur = listHead;
        int result = cur.val;
        int count = 1;

        while (cur.next != null) {
            cur = cur.next;
            count++;
            if (rand.nextInt(count) == 0) {
                result = cur.val;
            }
        }

        return result;
    }
}

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