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

  • 0
     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;
            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.