382. Linked List Random Node

Problem

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.

Implement the Solution class:

Solution(ListNode head) Initializes the object with the head of the singly-linked list head.
int getRandom() Chooses a node randomly from the list and returns its value. All the nodes of the list should be equally likely to be chosen.

https://leetcode.com/problems/linked-list-random-node/

Example 1:

case1

Input
["Solution", "getRandom", "getRandom", "getRandom", "getRandom", "getRandom"]
[[[1, 2, 3]], [], [], [], [], []]
Output
[null, 1, 3, 2, 2, 3]
Explanation
1
2
3
4
5
6
7
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.

Constraints:

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

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?

Test Cases

# 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]):


    def getRandom(self) -> int:



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

solution_test.py

import pytest

import os
import sys
sys.path.append(os.path.dirname(os.path.dirname(__file__)))
from _utils.linked_list import build_linked_list
from solution import Solution
from solution2 import Solution as Solution2

null = None


@pytest.mark.parametrize('actions, params, expects', [
    (
        ["Solution", "getRandom", "getRandom", "getRandom", "getRandom", "getRandom"],
        [[[1, 2, 3]], [], [], [], [], []],
        [null, 1, 3, 2, 2, 3],
    ),
])
@pytest.mark.parametrize('clazz', [Solution, Solution2])
def test_solution(clazz, actions, params, expects):
    sol = None
    for action, args, expected in zip(actions, params, expects):
        if action == 'Solution':
            nums = args[0]
            sol = clazz(build_linked_list(nums))
        elif action == 'getRandom':
            res = getattr(sol, action)(*args)
            if res != expected:
                assert res in nums
        else:
            assert getattr(sol, action)(*args) == expected

Thoughts

Solution 类在构造的时候，直接用数组记录下链表中的所有数字。每次调用 getRandom 随机选取其中一个返回即可。

__init__ 的时间复杂度 O(n)，getRandom 的时间复杂度 O(1)，整体空间复杂度 O(n)。

Code

solution.py

from random import choice
from typing import Optional


# 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._nums = []
        while head:
            self._nums.append(head.val)
            head = head.next

    def getRandom(self) -> int:
        return choice(self._nums)


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

O(1) Space

如果要 O(1) 空间复杂度，可以在构造的时候只记录链表的总长度。每次调用 getRandom 生成一个随机位置，遍历链表到指定位置的节点并返回其值即可。

__init__ 的时间复杂度 O(n)，getRandom 的时间复杂度 O(n)，整体空间复杂度 O(1)。

solution2.py

from random import randrange
from typing import Optional


# 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
        self._n = 0
        while head:
            self._n += 1
            head = head.next

    def getRandom(self) -> int:
        node = self._head
        choose = randrange(self._n)
        for _ in range(choose):
            node = node.next

        return node.val


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

本文除了题目描述（Problem）部分之外，其他内容由 Calf 原创，采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。