My accepted Java solution based on randomization.


  • 0
    O
    public class Solution {
        int size;
        ListNode list;
        /** @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) {
            size = 0;
            ListNode tmp = head;
            list = head;
            while(tmp != null) {
                tmp = tmp.next;
                size++;
            }
        }
        
        /** Returns a random node's value. */
        public int getRandom() {
            if (list == null) {
                return 0;
            }
            int rand = (int)(Math.random()*size);
            ListNode tmp = list;
            while(rand > 0 && tmp != null) {
                tmp = tmp.next;
                rand--;
            }
            
            return tmp == null ? (list == null ? 0 : list.val) : tmp.val;
        }
    }
    

Log in to reply
 

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