/* * @lc app=leetcode id=382 lang=cpp * * [382] Linked List Random Node */// @lc code=start/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */classSolution {public: ListNode *head_; /** @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. */intgetRandom() {int res =-1;auto cur = head_;for (int cnt =1; cur !=nullptr; cur =cur->next,++cnt) {if (rand() % cnt ==0) res =cur->val; }return res; }};/** * Your Solution object will be instantiated and called as such: * Solution* obj = new Solution(head); * int param_1 = obj->getRandom(); */// @lc code=end
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */classSolution {ListNode head; /** @param head The linked list's head. Note that the head is guaranteed to be not null, so it contains at least one node. */publicSolution(ListNode head) {this.head= head; } /** Returns a random node's value. */publicintgetRandom() {int res =-1;Random rand =newRandom();int count =0;ListNode node = head;while (node !=null) {if (rand.nextInt(++count) ==0) { res =node.val; } node =node.next; }return res; }}/** * Your Solution object will be instantiated and called as such: * Solution obj = new Solution(head); * int param_1 = obj.getRandom(); */