382. Linked List Random Node

Description

The problem is about selecting a random node from a singly linked list. Since the list's length is unknown initially, the challenge is to find an efficient way to retrieve random nodes. The solution should ensure that each node has an equal probability of being chosen.

Intuition

The simplest way to randomly access nodes in a linked list is to first convert the list into an array (or any other data structure with constant-time access). Once stored in this manner, selecting a random element becomes trivial. This approach avoids the need to traverse the list multiple times while providing efficient random access.

Approach

1. Initialization: - Traverse the entire linked list once and store the nodes in a list or array. - This allows constant-time random access to any node.
2. Random Selection: - When the getRandom() function is called, generate a random index within the bounds of the array. - Return the node's value at this randomly chosen index.
3. Efficiency: - Storing all nodes in an array requires only a single traversal of the list. - Accessing any node is then reduced to O(1) time using random indexing.
4. Edge Cases: - If the list is empty (though it's usually assumed that the list has at least one node), we should handle such cases in real-world scenarios.

Complexity

Time Complexity:

• Initialization: O(n), where n is the number of nodes in the linked list.
• Random Selection: O(1), as accessing an array element by index is a constant-time operation.

Space Complexity:

O(n), where n is the number of nodes, since we store all the nodes in an array.

Code

C++

class Solution {
public:
    vector res;
    int length;

    Solution(ListNode* head) {
        ListNode* curr = head;
        while (curr != nullptr) {
            res.push_back(curr);
            curr = curr->next;
        }
        length = res.size();
    }

    int getRandom() {
        int index = rand() % length;
        return res[index]->val;
    }
};

Python

class Solution:

    def __init__(self, head: ListNode):
        self.res = []
        curr = head
        while curr:
            self.res.append(curr)
            curr = curr.next
        self.length = len(self.res)

    def getRandom(self) -> int:
        index = random.randint(0, self.length - 1)
        return self.res[index].val

Java

class Solution {
    private ArrayList res;
    private int length;
    private Random random;

    public Solution(ListNode head) {
        res = new ArrayList<>();
        ListNode curr = head;
        while (curr != null) {
            res.add(curr);
            curr = curr.next;
        }
        length = res.size();
        random = new Random();
    }

    public int getRandom() {
        int index = random.nextInt(length);
        return res.get(index).val;
    }
}

JavaScript

var Solution = function (head) {
    this.res = [];
    let curr = head;

    while (curr !== null) {
        this.res.push(curr)
        curr = curr.next;
    }
    this.length = this.res.length;
};

Solution.prototype.getRandom = function () {
    return this.res[Math.floor(Math.random() * this.length)].val
};