Without Fancy Algorithms : JAVA O(max(n,k))Time,O(1) Space.


  • 0
    G
     public Solution(ListNode head) {
            this.head = head;
            rand = new Random();
        }
        
        public int getRandom() {
            int count =0;
            ListNode curr = head;
            ListNode purr = head;
            //Iterate over the array to find the size in O(n) and get a random out of thoese val
            while(curr.next != null){
                curr = curr.next;
                count++;
            }
            int val = rand.nextInt(count+1);
            //Iterate over K elements and find the random value;
            for(int i=0; i<val; i++){
                purr = purr.next;  
            }
            return purr.val;  
    

Log in to reply
 

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