js 蓄水池算法

1. 单链表随机找一个节点，单链表长度未知，并且可能整个长度无法全部放入内存。

<script>
function ListNode(val, next) {
    this.val = (val===undefined ? 0 : val)
    this.next = (next===undefined ? null : next)
}
var head = new ListNode(1) ;
head.next = new ListNode(2);
head.next.next = new ListNode(3);
head.next.next.next = new ListNode(4);
head.next.next.next.next = new ListNode(5);
head.next.next.next.next.next = new ListNode(6);
head.next.next.next.next.next.next = new ListNode(7);
head.next.next.next.next.next.next.next = new ListNode(8);
head.next.next.next.next.next.next.next.next = new ListNode(9);
var Solution = function(head) {
     this.head = head;
};

 
Solution.prototype.getRandom = function() {
   var num = this.head.val;
   var next = this.head.next;
   var count = 1; 
   while(next){
      var ranNum = parseInt((count+1) *Math.random());// 随机[0,count] 之间的数字
      if(ranNum < 1){ // 因为是从单链表找一个节点，所以小于1，要是是蓄水池的长度是m的话，应该 ranNum < m,相应的num应该是一个数组类型
          num = next.val;
      }
      next = next.next;
      ++count;
   }
   return num;
};
//从单链表中随机寻找m个节点返回。
Solution.prototype.getRandom2 = function(m) {
 
   if(!m){ return []}
   var arr = [];
   var next = this.head;
   for(var i=0; i<m; i++){
      arr.push(next.val);
      next = next.next;
      if(!next){
        break;
      }
   }
   var count = m;
   while(next){
      var ranNum = parseInt((count+1) *Math.random())
      if(ranNum < m){
          arr[ranNum] = next.val;
      }
      next = next.next;
      ++count;
   }
   return arr;
};
var solution = new Solution(head);
var param1 = solution.getRandom();
var param2 = solution.getRandom2(3); 
</script>