LC 382

Solution to LeetCode 382 Linked List Random Node.

LeetCode 382

Linked List Random Node (Medium). [link]

1. Use choice() to randomly select a node from an array.

   Time complexity O(N). Time complexity O(N).

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):

    def __init__(self, head):
        """
        :type head: Optional[ListNode]
        """
        self.array = []
        while head:
            self.array.append(head.val)
            head = head.next

    def getRandom(self):
        """
        :rtype: int
        """
        return choice(self.array)

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

2. Reservoir sampling. Randomly select k=1 sample from N samples. This approach can reduce the space complexity to O(1). Time complexity O(N). Space complexity O(1).

class Solution(object):

    def __init__(self, head):
        """
        :type head: Optional[ListNode]
        """
        self.head = head

    def getRandom(self):
        """
        :rtype: int
        """
        count, result = 0, 0
        cur = self.head
        while cur:
            count += 1
            if random.randint(1, count) == count: # select one integer from [1,count) 
                result = cur.val
            cur = cur.next
        return result

Note: Randomly select a number in a range: random.randint(a,b), a inclusive and b inclusive. random.randrange(a,b), a inclusive and b exclusive.