Solution with using list size, O(1) space and O(n) time


  • 0
    V
    import java.util.Random;
    public class Solution {
    
        private ListNode head;
        private Random random;
        private int listSize;
        
        /** @param head The linked list's head. Note that the head is guanranteed to be not null, so it contains at least one node. */
        public Solution(ListNode head) {
            this.head=head;
            random=new Random();
            sizeOfList();
        }
        
        private void sizeOfList(){
            for(ListNode node=head;node!=null;node=node.next)
                listSize++;
        }
        
        /** Returns a random node's value. */
        public int getRandom() {
            int index=random.nextInt(listSize);
            ListNode node=head;
            while(index>0){
                node=node.next;
                if(index%2==0){
                    node=node.next;
                    index-=2;
                }
                else
                    index--;
            }
            //
            return node.val;
        }
    }
    
    /**
     * 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.