@@ -0,0 +1,2115 @@
+package com.freetymekiyan.algorithms.level.medium;%0A%0Aimport com.freetymekiyan.algorithms.utils.Utils.ListNode;%0A%0Aimport java.util.Random;%0A%0A/**%0A * Given a singly linked list, return a random node's value from the linked list. Each node must have the same%0A * probability of being chosen.%0A * %3Cp%3E%0A * Follow up:%0A * What if the linked list is extremely large and its length is unknown to you? Could you solve this efficiently without%0A * using extra space?%0A * %3Cp%3E%0A * Example:%0A * %3Cp%3E%0A * // Init a singly linked list %5B1,2,3%5D.%0A * ListNode head = new ListNode(1);%0A * head.next = new ListNode(2);%0A * head.next.next = new ListNode(3);%0A * Solution solution = new Solution(head);%0A * %3Cp%3E%0A * // getRandom() should return either 1, 2, or 3 randomly. Each element should have equal probability of returning.%0A * solution.getRandom();%0A * %3Cp%3E%0A * Tags: Reservoir Sampling%0A */%0Apublic class LinkedListRandomNode %7B%0A%0A    /**%0A     * Definition for singly-linked list.%0A     * public class ListNode %7B%0A     * int val;%0A     * ListNode next;%0A     * ListNode(int x) %7B val = x; %7D%0A     * %7D%0A     */%0A    class Solution %7B%0A%0A        private final ListNode head;%0A        private final Random r;%0A        private ListNode current;%0A%0A        /**%0A         * @param head The linked list's head.%0A         *             Note that the head is guaranteed to be not null, so it contains at least one node.%0A         */%0A        public Solution(ListNode head) %7B%0A            this.head = head;%0A            this.current = head;%0A            r = new Random();%0A        %7D%0A%0A        /** Returns a random node's value. */%0A        public int getRandom() %7B%0A            int res = head.val;%0A            ListNode n = head.next;%0A            int i = 2;%0A            while (n != null) %7B%0A                if (r.nextInt(i) == 0) %7B // For ith item, with probability 1/i, replace with new item.%0A                    res = n.val;%0A                %7D%0A                n = n.next;%0A                i++;%0A            %7D%0A            return res;%0A        %7D%0A    %7D%0A%0A/**%0A * Your Solution object will be instantiated and called as such:%0A * Solution obj = new Solution(head);%0A * int param_1 = obj.getRandom();%0A */%0A%7D%0A

add Linked List Random Node