# 382. Linked List Random Node [Accepted]

• Method 1: Time Complexity for `getRandom()` is O(N) & Space Complexity O(1)
Overall time complexity is still O(N).

I am calculating the value `k` which is the length of the LinkedList. Then, I generate a random number within the range `k` and simply traversing the list till that random number and return the value of the traversed node.

``````int k;
public Solution(ListNode head) {
k = 0;
while(head != null) {
k++;
}
}

/** Returns a random node's value. */
public int getRandom() {
int rand = (int)(Math.random() * k);
ListNode node = head;
int result = node.val;

while(node != null && rand != 0) {
rand--;
node = node.next;
}
return node != null ? node.val : result;
}
``````

Method 2: Time Complexity for `getRandom()` is O(1) & Space Complexity O(N)
Overall time complexity is still O(N).
Instead of traversing the list at `getRandom()` as we saw in Method 1, we can simply add the values from LinkedList to a separate array or ArrayList.
Then, generate a random number equivalent to the list size and retrieve the element from the list at the position of random number.

``````ListNode head;
List<Integer> list;
public Solution(ListNode head) {
list = new ArrayList<>();

while(head != null) {