Easy to understand c++: reservoir


  • 0
    C
    class Solution {
        public:
            /** @param head The linked list's head. Note that the head is guanranteed to be not null, so it contains at least one node. */
            Solution(ListNode* h) {
                head = h;
            }
            
            /** Returns a random node's value. */
            int getRandom() {
                ListNode* cur = head;
                int result = head->val;
                for (int i = 1; cur; i++) {
                    if (rand()%i == 0) result = cur->val; // 1/i probability to change
                    cur = cur->next;
                }
                return result;
            }
        private:
            ListNode* head;
        };

Log in to reply
 

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