O(n) time, O(1) space


  • 0
    R

    I realized that this is very similar to the problem to picking a random number from a stream. For both problems, you don't know what the length of the linked list or the stream and it can be solved with constant memory.

    The algorithm is as follows:
    Iterate through all the nodes in the linked list while keep track of the index of the node in base 1. So the first node with have a number of 1, the second will have a number of 2.

    For every node, let there be a probability of 1/(base 1 index of node) of it being picked.

    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 rand; 
    
        public Solution(ListNode head) {
            this.head = head;
            rand = new Random();
        }
        
        /** Returns a random node's value. */
        public int getRandom() {
            ListNode result = null;
            ListNode cand = this.head;
            int count = 1;
            while(cand != null) {
                if(shouldBePicked(count)) {
                    result = cand;
                }
                cand = cand.next;
                count++;
            }
            
            return result.val;
        }
        
        public boolean shouldBePicked(int denom) {
            int value = this.rand.nextInt(denom);
            return value == 0;
        }
     }
    

Log in to reply
 

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