My C Solution no using reservoir sampling


  • 0
    M
    /**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     struct ListNode *next;
     * };
     */
    typedef struct {
        struct ListNode* head;
        int length;
    } Solution;
    
    /** @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* solutionCreate(struct ListNode* head) {
        Solution* obj = (Solution*)malloc(sizeof(Solution));
        obj->head = head;
        obj->length = 0;
        while(head){obj->length++; head = head->next;}
        return obj;
    }
    
    /** Returns a random node's value. */
    int solutionGetRandom(Solution* obj) {
        int n = rand() % (obj->length)+1;
        int i = 1;
        struct ListNode* p = obj->head;
        for (; p && i < n; p = p->next, i++);
        return p->val;
    }
    
    void solutionFree(Solution* obj) {
        free(obj);
    }
    
    /**
     * Your Solution struct will be instantiated and called as such:
     * struct Solution* obj = solutionCreate(head);
     * int param_1 = solutionGetRandom(obj);
     * solutionFree(obj);
     */
    

Log in to reply
 

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