Linked List Random Node — LeetCode 382 Python Solution

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

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