time O(n) C++ solution


  • 0
    K
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     ListNode *next;
     *     ListNode(int x) : val(x), next(NULL) {}
     * };
     */
    class Solution {
    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) {
            h=head;
        }
        
        /** Returns a random node's value. */
        int getRandom() {
            int cnt=1;
            ListNode*p=h;
            int res=0;
            while(p)
            {
                int n=rand()%cnt;
                if(n==0)
                    res=p->val;
                p=p->next;
                cnt++;
            }
            return res;
        }
    private:
        ListNode* h;
    };
    
    /**
     * Your Solution object will be instantiated and called as such:
     * Solution obj = new Solution(head);```
     * int param_1 = obj.getRandom();
     */

Log in to reply
 

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