382. Linked List Random Node LeetCode Solution

Last updated: February 17, 2025

In this guide, you will get 382. Linked List Random Node LeetCode Solution with the best time and space complexity. The solution to Linked List Random Node problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Linked List Random Node solution in C++
Linked List Random Node solution in Java
Linked List Random Node solution in Python
Additional Resources

382. Linked List Random Node LeetCode Solution image

Problem Statement of Linked List Random Node

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].
-104 <= Node.val <= 104
At most 104 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?

Complexity Analysis

Time Complexity: O(n)
Space Complexity: O(1)

382. Linked List Random Node LeetCode Solution in C++

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 res = -1;
    int i = 1;

    for (ListNode* curr = head; curr; curr = curr->next, ++i)
      if (rand() % i == 0)
        res = curr->val;

    return res;
  }

 private:
  ListNode* head;
};
/* code provided by PROGIEZ */

382. Linked List Random Node LeetCode Solution in Java

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 res = -1;
    int i = 1;

    for (ListNode curr = head; curr != null; curr = curr.next, ++i)
      if (rand.nextInt(i) == i - 1)
        res = curr.val;

    return res;
  }

  private ListNode head;
  private Random rand = new Random();
}
// code provided by PROGIEZ

382. Linked List Random Node LeetCode Solution in Python

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

class Solution:
  def __init__(self, head: ListNode | None):
    self.head = head

  def getRandom(self) -> int:
    res = -1
    i = 1
    curr = self.head

    while curr:
      if random.randint(0, i - 1) == 0:
        res = curr.val
      curr = curr.next
      i += 1

    return res
 # code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.

Table of Contents