Leetcode 382. 链表随机节点

题目

给定一个单链表，随机选择链表的一个节点，并返回相应的节点值。保证每个节点被选的概率一样。

示例:

// 初始化一个单链表 [1,2,3]. ListNode head = new ListNode(1); head.next = new ListNode(2); head.next.next = new ListNode(3); Solution solution = new Solution(head); // getRandom()方法应随机返回1,2,3中的一个，保证每个元素被返回的概率相等。 solution.getRandom();

题解

哈希表记录结点，随机选取

代码

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: int len; unordered_map<int,ListNode*> list; /** @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) { len = 0; ListNode *p = head; while(p){ list[len] = p; len++; p = p->next; } } /** Returns a random node's value. */ int getRandom() { return list[random() % len]->val; } }; /** * Your Solution object will be instantiated and called as such: * Solution* obj = new Solution(head); * int param_1 = obj->getRandom(); */

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/linked-list-random-node 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。