2020 December LeetCoding Challenge

문제

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.

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?

linked list 가 주어지고 list 의 노드 중 랜덤한 노드의 값을 반환하는 문제. 모든 노드는 같은 확률로 선택되어야한다.

Follow up
문제를 해결하는데 추가 공간이 필요하다면 linked list 가 어마무시하게 클때 공간복잡도도 어마무시하게 늘어난다. 추가적인 공간을 사용하지 않고 문제를 풀어보자.

풀이

class Solution {
    private readonly root: ListNode;
    constructor(head: ListNode | null) {
        if (!head) {
            throw Error('head is null');
        }
        this.root = head;
    }

    getRandom(): number {

        let current: ListNode | null = this.root;
        let k = 1;

        let random = 0;
        while (current) {
            // random 1 to k
            if (Math.random() * k <= 1) {
                random = current.val;
            }
            k++;
            current = current.next;
        }
        return random;
    }
}

간단한 수학 공식을 사용하면 해결 할 수 있다.

노드의 개수를 n 이라고 하고
순회중인 현재 노드가 k 라고 할때
n = 1
k = 1 일때 1 번째 노드가 선택될 확률은 100%

n = 2
k = 1 = 1/1 * 1/2 = 50%
k = 2 = 1/2 = 50%

n = 3
k = 1 = 1/1 x 1/2 x 1/3 = 33.33%
k = 2 = 1/2 x 1/3 = 33.33%
k = 3 = 1/3 = 33.33%

...

Cost

Time complexity = O(n)
Space complexity = O(1)