Java follow-up O(N) time O(1) space.


  • 0
    public class Solution {
        ListNode root;
        /** @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) {
            root = head;
        }
        /** Returns a random node's value. */
        public int getRandom() {
            ListNode cur = root;
            int count=1;
            int ret = cur.val;
            while (cur.next != null) {
                cur=cur.next;
                double chance = (double) 1 / (double) (count+1);
                double rand = Math.random();
                count++;
                if ( rand <= chance) ret = cur.val;
            }
            return ret;
        }
    }
    

Log in to reply
 

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