Leetcode 382. 链表随机节点 解题思路及C++实现

解题思路：

因为题目中要求需要常数级的空间复杂度，所以就需要计算链表长度了。

 

/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode(int x) : val(x), next(NULL) {}* };*/ class Solution { public:int n = 0; //用于记录链表长度，用于实现等概率ListNode* root;/** @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) {root = head;while(head){n++;head = head->next;}}/** Returns a random node's value. */int getRandom() {int tmp = 0 + rand() % n; //n是整数的范围ListNode* ln = root;while(tmp > 0){ln = ln->next;tmp--;}return ln->val;} };/*** Your Solution object will be instantiated and called as such:* Solution* obj = new Solution(head);* int param_1 = obj->getRandom();*/

 

 

总结

以上是生活随笔为你收集整理的Leetcode 382. 链表随机节点 解题思路及C++实现的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。