[C++]equal possibility without knowing length


  • 3
    L
    class Solution {
    public:
    Solution(ListNode* head) {
        h = head;
    }
    
    /** Returns a random node's value. */
    int getRandom() {
        int rd = 1;
        ListNode* tmp = h;
        ListNode* res = NULL;
        while(tmp){
            if(rand()%rd==0)
                res = tmp;
            tmp = tmp->next;
            rd++;
        }
        return res->val;
    }
    
    private:
    ListNode* h;
    

    };


  • 0
    H

    rd equals to the length of list.


Log in to reply
 

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