Java Solution in 2 ways: O(1) space or O(1) time getRandom()


  • 0
    E
    // O(1) space  O(n) getRandom()
    public class Solution {
        java.util.Random rand = new java.util.Random();
        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 p = head;
            while(p != null){
                p = p.next;
                len++;
            }
        }
         
        /** Returns a random node's value. */
        public int getRandom() {
            ListNode p = head;
            int k = rand.nextInt(len);
            int i = 0;
            while(i++ < k){
                p = p.next;
            }
            return p.val;
        }
    }
     
    
    // O(n) space  O(1) getRandom()
    public class Solution {
        java.util.Random rand = new java.util.Random();
        ArrayList<Integer> list;
         
        /** @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) {
            list = new ArrayList<Integer>();
            ListNode p = head;
            while(p != null){
                list.add(p.val);
                p = p.next;
            }
        }
         
        /** Returns a random node's value. */
        public int getRandom() {
            return list.get(rand.nextInt(list.size()));
        }
    }
    

Log in to reply
 

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