MediumNo. 0382
Linked List Random Node — LeetCode 382 Python Solution
- Pattern
- Linked List
- Topics
- Reservoir Sampling, Linked List, Math, Randomized
- Reading time
- 4 min
- Source
- leetcode.com
The 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.
Example
- Input
- ["Solution", "getRandom", "getRandom", "getRandom", "getRandom", "getRandom"]
- Output
- [null, 1, 3, 2, 2, 3]
- Explanation
- Solution solution = new Solution([1, 2, 3]);
Python solution
# 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
def getRandom(self) -> int:
n = ans = 0
head = self.head
while head:
n += 1
x = random.randint(1, n)
if n == x:
ans = head.val
head = head.next
return ans
# Your Solution object will be instantiated and called as such:
# obj = Solution(head)
# param_1 = obj.getRandom()Complexity
- Time
- O(n) or O(1)
- Space · auxiliary
- O(1)
Pattern: Linked List
Rewire pointers in place, with a dummy head and a saved next to keep it safe. LeetCode 382. Linked List Random Node is filed here because LeetCode tags it Linked List, which is the vocabulary this hub collects.
The linked list guide has the Python template for the pattern and the 75 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0384 | Shuffle an Array | Medium |
| 0002 | Add Two Numbers | Medium |
| 0470 | Implement Rand10() Using Rand7() | Medium |
| 0478 | Generate Random Point in a Circle | Medium |
| 1290 | Convert Binary Number in a Linked List to Integer | Easy |
| 1515 | Best Position for a Service Centre | Hard |
Frequently asked questions
- How hard is LeetCode 382. Linked List Random Node?
LeetCode 382. Linked List Random Node is rated Medium on LeetCode.
- What topics does LeetCode 382. Linked List Random Node cover?
LeetCode 382. Linked List Random Node is tagged Reservoir Sampling, Linked List, Math and Randomized on LeetCode.