Straight forward Java Solution.


  • 0
    J

    I think this question is quite straightforward. However, I am curious how to deal with the follow up... Without a length variable, I think the only way is to use Reservoir sampling, so that every node has the same chance. However, I am still confusing when is the time to output as this is not a stream...

    public class Solution {
        int len = 0;
        ListNode head;
        /** @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;
            ListNode cur = head;
            while(cur!=null){
                len++;
                cur = cur.next;
            }
        }
        
        /** Returns a random node's value. */
        public int getRandom() {
            int r = (int)(Math.random() * len);
            ListNode cur = head;
            while(r > 0){
                cur = cur.next;
                r--;
            }
            return cur.val;
        }
    }
    

Log in to reply
 

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