_382. Linked List Random Node.md

382. Linked List Random Node

All prompts are owned by LeetCode. To view the prompt, click the title link above.

Back to top

---

First completed : June 22, 2024

Last updated : June 22, 2024

---

Related Topics : Linked List, Math, Reservoir Sampling, Randomized

Acceptance Rate : 63.69 %

---

Solutions

• m382.c
• m382.java
• m382.py

C

m382.c

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */



typedef struct {
    struct ListNode* head;
    int size;
} Solution;


Solution* solutionCreate(struct ListNode* head) {
    int size = 0;
    struct ListNode* curr = head;
    while (curr) {
        curr = curr->next;
        size++;
    }

    Solution* output = (struct Solution*) malloc(sizeof(Solution));
    output->size = size;
    output->head = head;

    return output;
}

int solutionGetRandom(Solution* obj) {
    int indx = rand() % (obj->size);

    struct ListNode* curr = obj->head;
    for (int i = 0; i < indx; i++) {
        curr = curr->next;
    }

    return curr->val;

}


// I'm presuming that we don't need to free the linkedlist
// Since that was fed initially as an outside obj
void solutionFree(Solution* obj) {
    free(obj);
}

/**
 * Your Solution struct will be instantiated and called as such:
 * Solution* obj = solutionCreate(head);
 * int param_1 = solutionGetRandom(obj);
 
 * solutionFree(obj);
*/

Java

m382.java

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    private ListNode head;
    private int size;
    public Solution(ListNode head) {
        this.head = head;
        this.size = 0;

        ListNode curr = head;
        while (curr != null) {
            curr = curr.next;
            size++;
        }
    }
    
    public int getRandom() {
        int indx = (int) (Math.random() * size);
        ListNode curr = head;
        for (int i = 0; i < indx; i++) {
            curr = curr.next;
        }

        return curr.val;
    }
}

/**
 * Your Solution object will be instantiated and called as such:
 * Solution obj = new Solution(head);
 * int param_1 = obj.getRandom();
 */

Python

m382.py

# 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: Optional[ListNode]):
        self.head = head

        size = 0
        curr = head
        while curr :
            curr = curr.next
            size += 1
        print(size)
        self.size = size

    def getRandom(self) -> int:
        randIndx = randint(0, self.size - 1)

        output = self.head
        for _ in range(randIndx) :
            output = output.next

        return output.val


# Your Solution object will be instantiated and called as such:
# obj = Solution(head)
# param_1 = obj.getRandom()