package leetcode;

/**
 * https://leetcode.com/problems/linked-list-random-node/
 */
public class Problem382 {
    public static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }

    public static 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.
         */
        public Solution(ListNode head) {

        }

        /**
         * Returns a random node's value.
         */
        public int getRandom() {
            // TODO
            return 0;
        }
    }

    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        Solution solution = new Solution(head);

        System.out.println(solution.getRandom());
        System.out.println(solution.getRandom());
        System.out.println(solution.getRandom());
    }
}

@@ -12,16 +12,93 @@
 tcode;%0A%0A
+import java.util.ArrayList;%0Aimport java.util.List;%0Aimport java.util.Random;%0A%0A
 /**%0A * h
@@ -356,16 +356,133 @@
 ution %7B%0A
+        private final List%3CInteger%3E values = new ArrayList%3C%3E();%0A        private final Random random = new Random();%0A%0A
         
@@ -695,28 +695,20 @@
 ) %7B%0A
-%0A
     
-    %7D%0A%0A
         
 /**%0A
@@ -707,53 +707,68 @@
     
-/**%0A         * Returns a random node's value.
+for (ListNode node = head; node != null; node = node.next) %7B
 %0A   
@@ -768,36 +768,32 @@
 ) %7B%0A        
- */%0A
         
 public int g
@@ -784,32 +784,29 @@
     
-public int getRandom() %7B
+values.add(node.val);
 %0A   
@@ -818,15 +818,9 @@
     
-// TODO
+%7D
 %0A   
@@ -828,21 +828,10 @@
     
-    return 0;
+%7D%0A
 %0A   
@@ -839,328 +839,197 @@
     
-%7D
+/**
 %0A    
-%7D%0A%0A
     
-public static void main(String%5B%5D args) %7B%0A        ListNode head = new ListNode(1);%0A        head.next = new ListNode(2);%0A        head.next.next = new ListNode(3);%0A        Solution solution = new Solution(head);%0A%0A        System.out.println(solution.getRandom());%0A        System.out.println(solution
+ * Returns a random node's value.%0A         */%0A        public int getRandom() %7B%0A            int randomIdx = random.nextInt(values.size());%0A            return values
 .get
-R
+(r
 andom
-()
+Idx
 );%0A 
@@ -1039,49 +1039,9 @@
     
-System.out.println(solution.getRandom());
+%7D
 %0A   

Solve poblem 382