题目描述

题目链接：382. Linked List Random Node

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.

例子

例子 1

Input: ["Solution", "getRandom", "getRandom", "getRandom", "getRandom", "getRandom"] [[[1, 2, 3]], [], [], [], [], []] Output: [null, 1, 3, 2, 2, 3] Explanation: Solution solution = new Solution([1, 2, 3]); solution.getRandom(); // return 1 solution.getRandom(); // return 3 solution.getRandom(); // return 2 solution.getRandom(); // return 2 solution.getRandom(); // return 3 // getRandom() should return either 1, 2, or 3 randomly. Each element should have equal probability of returning.

Follow Up

• What if the linked list is extremely large and its length is unknown to you?
• Could you solve this efficiently without using extra space?

Constraints

• The number of nodes in the linked list will be in the range [1, 10^4].
• -10^4 <= Node.val <= 10^4
• At most 10^4 calls will be made to getRandom.

解题思路

这道题思路比较直观，首先记录链表的长度，每次随机去一个数字取对应的节点的值即可。

class Solution {
public:
    /** @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) {
        ListNode* curr = head;
        length_ = 0;
        while (curr) {
            length_++;
            curr = curr->next;
        }
    }

    /** Returns a random node's value. */
    int getRandom() {
        int step = rand() % length_;
        ListNode* ret = head_;
        while (step-- != 0) {
            ret = ret->next;
        }
        return ret->val;
    }

private:
    ListNode* head_;
    int length_;
};

• 时间复杂度: O(n)
• 空间复杂度: O(n)

GitHub 代码同步地址： 382.LinkedListRandomNode.cpp

其他题目： GitHub: Leetcode-C++-Solution 博客： Leetcode-Solutions