Problem Statement

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 integer array nums.

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 choosen.

Constraints:

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

Linear space complexity solution

A naive solution is to store all nodes in an ArrayList and then randomly pick an item:

class Solution:
    def __init__(self, head: ListNode):
        self.nodes = []
        current = head
        while current:
            self.nodes.append(current.val)
            current = current.next

    def getRandom(self) -> int:
        return random.choice(self.nodes)

The getRandom method has O(1) running time. What if the LinkedList is very long? Then self.nodes will consume a lot of memory.

Constant space complexity solution I

We associate each node with a random number and pick the node associated with the maximum number:

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

    def getRandom(self) -> int:
        current_max = -1
        val = None
        current = self.head
        while current:
            ran = random.random()
            if ran > current_max:
                current_max = ran
                val = current.val
            current = current.next
        return val

Constant space complexity solution II

Another constant space complexity solution uses Reservoir sampling. It’s a special case with k = 1.

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

    def getRandom(self) -> int:
        node = self.head
        res = None
        index = 0
        while node:
            current = random.randint(0, index)
            if current == index:
                res = node.val
            index += 1
            node = node.next
        return res

One advantange of this solution is it can be easily extended to cases with k > 1. For example, one can be asked to generate 5 random nodes. See a clean implementation here.

Related Posts

• Why head&tail pointers cannot point to the same node. Linear (singly) linked list