Leetcode Linked List Random Node problem solution

In this Leetcode Linked List Random Node problem solution you have 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.

Leetcode Linked List Random Node problem solution

Problem solution in Python.

class Solution:

    def __init__(self, head: ListNode):
        """
        @param head The linked list's head.
        Note that the head is guaranteed to be not null, so it contains at least one node.
        """
        self.values=[]
        while head:
            self.values.append(head.val)
            head=head.next

    def getRandom(self) -> int:
        """
        Returns a random node's value.
        """
        import random
        return self.values[random.randint(0,len(self.values)-1)]

Problem solution in Java.

class Solution {

List<Integer> arr = null;
Random rand;

public Solution(ListNode head) {
    ListNode ptr = head;
    this.arr = new ArrayList<>();
    while(ptr != null){
        arr.add(ptr.val);
        ptr = ptr.next;
    }
    this.rand = new Random();
}

/** Returns a random node's value. */
public int getRandom() {
    return this.arr.get(this.rand.nextInt(this.arr.size()));
}
}

Problem solution in C++.

class Solution {
public:
    vector<int>vec;
    Solution(ListNode* head) {
        while(head){
            vec.push_back(head->val);
            head = head->next;
        }
    }
    int getRandom() {
        return vec[rand()%vec.size()];
    }
};

Problem solution in C.

typedef struct {
    struct ListNode* head
} Solution;

Solution* solutionCreate(struct ListNode* head) {
    srand(time(NULL));
    Solution* sul = malloc(sizeof(Solution));
    sul->head=head;
    return sul;
}

int solutionGetRandom(Solution* obj) {
    
    int count = 0;
    struct ListNode* temp;
    struct ListNode* head;
    temp = obj->head;
    head = temp;
    int i;
    while(head!=NULL)
    {
        head=head->next;
        count++;
    }

    int  r= random()%count; 
    head = temp;
    for(i=0;i<r;i++)
    {
        head = head->next;
    }

    return head->val;
}

void solutionFree(Solution* obj) {
    free(obj);
}

coding problems solutions