single linked list가 있습니다.


노드는 이런식이라고 정의 되었다고 하죠.

struct node {

node *next;

int val;

};


우리에겐 node *head가 주어져 있습니다.

그리고 우리는 리스트의 랜덤한 임의의 노드를 리턴하고 싶습니다. 

단, 모든 노드는 같은 확률로 선택될수 있어야 합니다.

리스트에 몇개의 노드가 있는지는 모릅니다.


한번의 순회와 추가메모리의 사용없이 임의의 노드를 리턴하는 함수는?

(함수호출에 의한 스텍메모리 사용도 추가메모리 사용으로 간주)


node* get_random_node() {

// TO DO...

}


숙제 아닙니다. 이런 글 올리면 오해하는 분들이 계셔서..

그냥 좋은 알고리즘 문제인거 같아서 공유하는 겁니다.