Java O(1) space a little less than O(N) time by average via path compression (123 ms)


  • 0

    Instead of starting from the head all the time, we can start at the last selected node. When you know the size of the list, we first roll the dice to get the steps between 0 to size-1. If the steps go to the tail of the list. We move the node to the head and go through the rest steps after the tail.

    public class Solution {
        int count = 1;
        int idx = 0;
        Random rd = new Random();
        ListNode cur;
        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;
            cur = head;
            while (cur.next != null) {
                cur = cur.next;
                count++;
            }
            cur=head;
        }
        
        /** Returns a random node's value. */
        public int getRandom() {
            int steps = rd.nextInt(count);
            if ( (idx+steps) >= count){
                cur = root;
                steps = (idx+steps) - count;
                idx = 0;
            }
            while (steps > 0) {
                steps--;
                idx++;
                cur=cur.next;
            }
            return cur.val;
        }
    }
    

Log in to reply
 

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