Linked List Random Node [leetcode]

문제

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 integer array nums.
• 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 choosen.

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:

• The number of nodes in the linked list will be in the range [1, 10^4].
• -10^4 <= Node.val <= 10^4
• At most 10^4 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?

코드

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    
    import random
    head = None
    length = 0
    
    def __init__(self, head: Optional[ListNode]):
        self.head = head
        curr = head
        while curr != None:
            curr = curr.next
            self.length+=1
        # print(self.length)
        return None

    def getRandom(self) -> int:
        curr = self.head
        if self.length == 1:
            return curr.val
        else:
            idx = self.random.randrange(1,self.length+1)
            for i in range(idx-1):
                curr = curr.next
            return curr.val

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

 

문제 풀이

링크드 리스트에서 랜덤으로 숫자를 뽑는 문제이다.

엥? 그렇다면 배열하나 만들고, 해당 배열에서 랜덤한 숫자 뽑게 하면 쉽게 풀듯? 했다.

 

하지만 문제 follow up으로 나오는 조건을 다시 한번 보자.

Could you solve this efficiently without using extra space? → 메모리 추가적으로 쓰지마세요 휴먼

 

음... 그럼 배열 생성해서 인덱스로 접근하는건 못하는군

다음으로 생각한 로직은

1. 링크드 리스트 저장(head를 저장) 할때, 리스트를 순회하면서 리스트의 크기를 잰다

def __init__(self, head: Optional[ListNode]):
      self.head = head
      curr = head
      while curr != None:
          curr = curr.next
          self.length+=1 # 해당 리스트의 길이를 측정
      return None

1. 해당 길이를 통해 random 모듈로 랜덤한 숫자를 뽑는다. → index
2. 저장된 head를 통해 index만큼! loop 를 돌면서 해당자리에 val을 반환한다.

def getRandom(self) -> int:
    curr = self.head
    if self.length == 1:
        return curr.val
    else:
        idx = self.random.randrange(1,self.length+1)
        for i in range(idx-1):
            curr = curr.next
        return curr.val

 

그리고 그 결과는

실행시간은 다른사람 풀이에 비해 굉장히 느리지만,

follow up (추가적인 메모리 공간 할당x) 를 고려했더니 상위권이였다.