c++ easy solution with follow up solution


  • 1
    S
    class Solution {
    private:
        ListNode* curr;
        ListNode* newhead;
        int length;
    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) {
            curr = head;
            newhead = head;
            int i = 0;
            while(head){
                head = head->next;
                i++;
            }
            length = i;
        }
        
        /** Returns a random node's value. */
        int getRandom() {
            int n = rand() % length;
            while(n){
                if(!curr->next){
                    curr = newhead;
                    n--;
                }
                while(curr && curr->next && n){
                    curr = curr->next;
                    n--;
                }
            }
            return curr->val;
        }
    };
    
    

    Follow up Solution:

    class Solution {
    private:
        ListNode* curr;
        ListNode* newhead;
    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) {
            curr = head;
            newhead = head;
        }
        
        /** Returns a random node's value. */
        int getRandom() {
            int n = rand();
            while(n){
                if(!curr->next){
                    curr = newhead;
                    n--;
                }
                while(curr && curr->next && n){
                    curr = curr->next;
                    n--;
                }
            }
            return curr->val;
        }
    };
    
    

  • 0
    C

    Why the follow up solution working? Where is the initialization of n?
    Can you explain a little?
    Thanks.


  • 0
    S

    @cityboygary Thank you for noticing me. I add it to getrandom() function.


  • 0

    Now it gets "Time Limit Exceeded".


  • 0
    S

    @StefanPochmann Yes, the reason is that rand() could generate a "big" number.


Log in to reply
 

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