[leet code] Linked List Random Node (python)

Problem

Example 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.

 

Constraints:

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?

How to solve

구해야 하는것?

linked list 에서

list의 노드 중 랜덤라게 노드를 반환

모든 노드는 같은 확율로 선택

 

풀이

노드에 있는 값을 리스트에 담아주고, 

python의 random.choice() 함수를 이용해 값을 return

random.choice(리스트)를 하면 그 리스트에 있는 값을 랜덤하게 리턴해준다. 

파이썬 좋다

 

**주의 사항**

자료형 범위 주의!

 

Solution(python)

# 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: ListNode):
        """
        @param head The linked list's head.
        Note that the head is guaranteed to be not null, so it contains at least one node.
        """
        self.output = []
        while(head):
            self.output.append(head.val)
            head = head.next
        

    def getRandom(self) -> int:
        """
        Returns a random node's value.
        """
        return random.choice( self.output )
        


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

Test Result