Skip to main content

Linked List Random Node

Problem Description​

Given a singly linked list, return a random node's value from the linked list. Each node must have the same probability of being chosen.

Implement the Solution class:

Solution(ListNode head) Initializes the object with the head of the singly-linked list head. int getRandom() Chooses a node randomly from the list and returns its value. All the nodes of the list should be equally likely to be chosen.

Example 1:​

Input
["Solution", "getRandom", "getRandom", "getRandom", "getRandom", "getRandom"]
[[[1, 2, 3]], [], [], [], [], []]
Output
[null, 1, 3, 2, 2, 3]

Explanation:

Solution solution = new Solution([1, 2, 3]);
solution.getRandom(); // return 1
solution.getRandom(); // return 3
solution.getRandom(); // return 2
solution.getRandom(); // return 2
solution.getRandom(); // return 3
// getRandom() should return either 1, 2, or 3 randomly. Each element should have equal probability of returning.

Constraints:​

  • The number of nodes in the linked list will be in the range [1,104].[1, 104].
  • −104<=Node.val<=104-104 <= Node.val <= 104
  • At most 10^4 calls will be made to getRandom.

Follow up:​

  • What if the linked list is extremely large and its length is unknown to you?
  • Could you solve this efficiently without using extra space?

Algorithm​

The Solution class is designed to choose a random node's value from a linked list. Here is a high-level overview of the algorithm used in the class:

  1. Initialization:

    • Store the head of the linked list.
    • Compute the size of the linked list.
  2. Compute the Length (len method):

    • Traverse the linked list from the head to the end.
    • Count the number of nodes.
  3. Get Random Node Value (getRandom method):

    • Generate a random number within the range of the linked list size.
    • Traverse the linked list to the node at the position of the generated random number.
    • Return the value of that node.

C++ Code​

#include <cstdlib> // for rand()

// Definition for singly-linked list.
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};

class Solution {
private:
ListNode *head;
int size;

int len(ListNode* head) {
ListNode* mover = head;
int n = 0;
while (mover) {
n++;
mover = mover->next;
}
return n;
}

public:
Solution(ListNode* head) {
this->head = head;
size = len(head);
}

int getRandom() {
int move = rand() % size;
ListNode* mover = head;
while (move) {
mover = mover->next;
move--;
}
return mover->val;
}
};

Python Code​

import random

# Definition for singly-linked list.
class ListNode:
def __init__(self, x):
self.val = x
self.next = None

class Solution:
def __init__(self, head: ListNode):
self.head = head
self.size = self.len(head)

def len(self, head: ListNode) -> int:
mover = head
n = 0
while mover:
n += 1
mover = mover.next
return n

def getRandom(self) -> int:
move = random.randint(0, self.size - 1)
mover = self.head
while move:
mover = mover.next
move -= 1
return mover.val

Java Code​

import java.util.Random;

// Definition for singly-linked list.
class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; next = null; }
}

class Solution {
private ListNode head;
private int size;
private Random random;

public Solution(ListNode head) {
this.head = head;
this.size = len(head);
this.random = new Random();
}

private int len(ListNode head) {
ListNode mover = head;
int n = 0;
while (mover != null) {
n++;
mover = mover.next;
}
return n;
}

public int getRandom() {
int move = random.nextInt(size);
ListNode mover = head;
while (move > 0) {
mover = mover.next;
move--;
}
return mover.val;
}
}

JavaScript Code​

// Definition for singly-linked list.
function ListNode(val) {
this.val = val;
this.next = null;
}

class Solution {
constructor(head) {
this.head = head;
this.size = this.len(head);
}

len(head) {
let mover = head;
let n = 0;
while (mover !== null) {
n++;
mover = mover.next;
}
return n;
}

getRandom() {
const move = Math.floor(Math.random() * this.size);
let mover = this.head;
let steps = move;
while (steps > 0) {
mover = mover.next;
steps--;
}
return mover.val;
}
}