Java two solutions, easy to understand


  • 3
    Y

    The first solution is the trivial one,

    we just count the length of the list, and then return a random number "r" between 0 and length,

    then we traverse the list again and stop at"r" steps and then return the value of that ListNode.

    public class Solution {
    
        /** @param head The linked list's head.
            Note that the head is guaranteed to be not null, so it contains at least one node. */
        int count = 0;
        ListNode head;
        public Solution(ListNode head) {
            this.head = head;
            ListNode tem = head;
            while(tem != null) {
                count++;
                tem = tem.next;
            }
        }
        
        /** Returns a random node's value. */
        public int getRandom() {
            ListNode fakehead = head;
            Random r = new Random();
            int random = r.nextInt(count);
            for (int i = 0; i < random; i++) {
                fakehead = fakehead.next;
            }
            return fakehead.val;
        }
    }
    

    Another one only traverse the list once, and we don't need to know the length of the list.

    public class Solution {
    
        /** @param head The linked list's head.
            Note that the head is guaranteed to be not null, so it contains at least one node. */
        ListNode head;
        Random random;
        public Solution(ListNode head) {
            this.head = head;
            random = new Random();
        }
        
        /** Returns a random node's value. */
        public int getRandom() {
            int count = 0;
            int result = -1;
            ListNode dummyhead = head;
            while(dummyhead != null) {
                if(random.nextInt(++count) == 0) {
                    result = dummyhead.val;
                }
                dummyhead = dummyhead.next;
            }
            return result;
        }
    }
    

    prof: for example: we have 3 numbers : 1,2,3.
    step 1: we pick 1 probability 1/1 .
    step 2: we have 1/2 probability to pick 2, so there are 1/2 chance we return 1 and 1/2 chance return 2.
    step 3: we have 1/3 probability to pick 3, and the probability that we return 2 is that we pick 2 in step 2 and don't pick 3 and step 3, so the probability of returning 2 is 1/2 * (1- 1/3) = 1/3. so in step 3 we have 1/3 chance to return 1, 1/3 chance to return 2, and 1/3 chance to return 3.


Log in to reply
 

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