# 382. Linked List Random Node

• Time: $O(n)$
• Space: $O(1)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 class Solution { public: /** @param head The linked list's head. Note that the head is guaranteed to be not null, so it contains at least one node. */ Solution(ListNode* head) : head(head) {} /** Returns a random node's value. */ int getRandom() { int ans = -1; int i = 1; for (ListNode* curr = head; curr; curr = curr->next, ++i) if (rand() % i == 0) ans = curr->val; return ans; } private: ListNode* head; }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 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) { this.head = head; } /** Returns a random node's value. */ public int getRandom() { int ans = -1; int i = 1; for (ListNode curr = head; curr != null; curr = curr.next, ++i) if (rand.nextInt(i) == i - 1) ans = curr.val; return ans; } private ListNode head; private Random rand = new Random(); }