C++ Solution - O(n) Time & O(1) space


  • 0
    S

    Suggestions for improvement are welcome!

    class Solution {
        ListNode* HEAD;
        int len;
    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* head) {
            this->HEAD = head;
            len = 0;
            while(head){
                len++;
                head = head->next;
            }
        }
        
        /** Returns a random node's value. */
        int getRandom() {
            ListNode* h = this->HEAD;
            int m = rand() % len;
            while(m--){
                h = h->next;
            }
            return h->val;
        }
    };
    
    /**
     * Your Solution object will be instantiated and called as such:
     * Solution obj = new Solution(head);
     * int param_1 = obj.getRandom();
     */
    

  • 0
    B

    O(n) space & O(1) Time ,haha

    class Solution {
    public:
        vector<int> v;
        Solution(ListNode* head) {
            while(head)
            {   v.push_back(head->val);
                head = head->next; 
            }
        }
        
        int getRandom() {
               return v[rand()%v.size()];
        }
    };
    

Log in to reply
 

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