[LeetCode][JS]Linked List Random Node

문제

문제: https://leetcode.com/explore/challenge/card/december-leetcoding-challenge/569/week-1-december-1st-december-7th/3552/

linked list가 주어지면 Nodes 중 랜덤으로 node's value를 출력하는 getRandom함수를 만들어라.

ex)
linked list : {"val":1,"next":{"val":2,"next":{"val":3,"next":null}}}

getRandom() -> 1
getRandom() -> 3
getRandom() -> 3
getRandom() -> 2

node'value를 랜덤하게 출력해주는 getRandom 함수를 만드는 문제이다.

해결방법

1. linked list를 순회하면서 value값만 모아둔 array를 만든다. (getVal())
2. 그 array를 이용해 Math.random() 을 이용해 인덱스를 랜덤으로 선택해서 출력한다. (getRandom())

문제에서 Solution을 생성자함수로 작성했고 getRandom을 Solution의 메소드로 작성했기 때문에 Solution의 프로퍼티(this.head, this.valList)를 메소드에 이용해서 해결했다.

code

var Solution = function(head) {
    this.head=head
    this.valList = this.getVal(head)
};

Solution.prototype.getRandom = function() {
    const randomIdx = Math.floor(Math.random()*this.valList.length)
    return this.valList[randomIdx]
};
Solution.prototype.getVal = function(root,val=[]){
    if(!root) return val
    else {
        val.push(root.val)
        Solution.prototype.getVal(root.next,val)
    }
    return val
}