My C++ 52ms solution


  • 0
    Y
    class Solution {
    public:
        ListNode* root;
        int n;
        /** @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) {
            root=head;
            n=0;
            while(head){
                head=head->next;
                n++;
            }
        }
        
        /** Returns a random node's value. */
        int getRandom() {
            ListNode* node=root;
            int m=n;
            while(rand()%(m--))node=node->next;
            return node->val;
        }
    };
    

Log in to reply
 

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