Hack University
318/670

318. Linked List Random Node

Medium

You receive the head of a singly linked list and an integer seed. Build a class Solution that is constructed once with (head, seed) and then answers any number of getRandom() calls, each returning the value of one node picked uniformly at random.

A checker cannot grade true randomness, so the random source is pinned. Keep an integer state, starting at seed. One draw in the range 0 … m − 1 works like this:

  1. update state = (state × 1103515245 + 12345) mod 2³¹
  2. the drawn number is state mod m

Every getRandom() call must make exactly one draw k = draw(n), where n is the number of nodes, and return the value of the k-th node counted from the head (0-indexed). The state carries over from one call to the next.

Follow-up: can you serve the calls without copying the list into an array — using only O(1) extra memory?

Three getRandom() calls on head = [10, 1, 42, 7] with seed = 7Each call makes one draw: the state is updated first, then reduced mod n = 4 to pick an index. Draws 0, 1, 2 select the nodes holding 10, 1, and 42.
seed = 7, n = 410index 01index 142index 27index 3call 1: state → 1282168116, k = 0returns 10call 2: state → 642666333, k = 1returns 1call 3: state → 712265938, k = 2returns 42state = (state × 1103515245 + 12345) mod 2^31, then k = state mod 4

Example 1:

Input: head = [10, 1, 42, 7], seed = 7, then 3 × getRandom()

Output: [10, 1, 42]

Explanation: The three draws step the state 7 → 1282168116 → 642666333 → 712265938, giving k = 0, 1, 2 (mod 4) — the nodes holding 10, 1, and 42.

Example 2:

Input: head = [5], seed = 123, then 4 × getRandom()

Output: [5, 5, 5, 5]

Explanation: With a single node every draw is k = 0 (anything mod 1 is 0), so each call returns 5 — but the state still advances four times.

Constraints:

  • 1 ≤ number of nodes ≤ 10⁴
  • -10⁴ ≤ Node.val ≤ 10⁴
  • 0 ≤ seed < 2³¹
  • 1 ≤ q ≤ 100 getRandom() calls
  • The product state * 1103515245 exceeds 32 bits — use 64-bit arithmetic.

Hints:

n is never handed to you — the constructor only gets head. Traverse the list once up front and remember how many nodes it has.

Easiest correct design: copy every value into an array in the constructor; each call is then one draw plus one index lookup. For the O(1)-memory follow-up, store only head and n: draw k = draw(n), then follow next exactly k times.

▶ Run checks these sample cases. Submit also runs hidden edge cases.

Input: head = [10, 1, 42, 7], seed = 7, calls = 3

Expected output: [10, 1, 42]