JAVA_LeetCode 382_Linked List Random Node 풀이 class Solution { private ListNode head; private Random rand; public Solution(ListNode head) { this.head = head; this.rand = new Random(); } public int getRandom() { int res = -1; ListNode curr = head; int cnt = 1; // 현재까지 센 노드 숫자 (1부터 시작) while (curr != null) { // 1/n(균등성)을 맞추기 위해 0일때 true로 적용 if(rand.nextInt(cnt) == 0) res = curr.val; curr = curr.next; cnt++; } return res; } } listNode, random, Reservoir Sampling(저수지 샘플링) 반환될 노드의 균등성(1/cnt)를 보장하는 방법 ...
