My solution with random number generation


  • 0

    Still working on the Reservoir Sampling, but this solution is much more easier to understand and quite straight forward. Hope it helps.

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

Log in to reply
 

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