Simple C++ reservoir solution needn't known the length of the list


  • 0
    C
    /**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     ListNode *next;
     *     ListNode(int x) : val(x), next(NULL) {}
     * };
     */
    class Solution {
    private:
        ListNode *_head;
    public:
        /** @param head The linked list's head.
            Note that the head is guaranteed to be not null, so it contains at least one node. */
        Solution(ListNode* head) {
            _head = head;
        }
        
        /** Returns a random node's value. */
        int getRandom() {
            ListNode *ret = _head;
            ListNode *cur = _head->next;
            int count = 1;
            while (cur != NULL) {
                ++count;
                int rnd = random() % count;
                if (rnd == 0)
                    ret = cur;
                cur = cur->next;
            }
            
            return ret->val;
        }
    };
    

    Reference: Reservoir sampling
    For detailed explanation: My Blog


Log in to reply
 

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