题目

题目来源：力扣（LeetCode）

给定一个单链表，随机选择链表的一个节点，并返回相应的节点值。保证每个节点被选的概率一样。

进阶:
如果链表十分大且长度未知，如何解决这个问题？你能否使用常数级空间复杂度实现？

示例:

  1. // 初始化一个单链表 [1,2,3].
  2. ListNode head = new ListNode(1);
  3. head.next = new ListNode(2);
  4. head.next.next = new ListNode(3);
  5. Solution solution = new Solution(head);
  7. // getRandom()方法应随机返回1,2,3中的一个，保证每个元素被返回的概率相等。
  8. solution.getRandom();

思路分析

蓄水池考虑的是如何循环一次随机取出对应的值
1、链表长度为n，随机抽取的目标节点为target，我们循环访问这个链表。
2、访问到第1个节点，我们则在[1,1]选取节点，第1个节点则为目标节点target。
3、访问到第2个节点，我们则在[1,2]选取节点，如果随机选择的节点是2，则目标节点为索引2的节点， 否则节点不变。
4、访问到第3个节点，我们则在[1,3]选取节点，如果随机选择的节点是3，则目标节点为索引3的节点， 否则节点不变。
5、访问到……
6、访问到第n个节点，我们则在[1,n]随机选取节点，如果随机选择的节点是n,则目标节点为索引n的节 点，否则节点不变 。

  1. /**
  2.  * Definition for singly-linked list.
  3.  * function ListNode(val, next) {
  4.  *     this.val = (val===undefined ? 0 : val)
  5.  *     this.next = (next===undefined ? null : next)
  6.  * }
  7.  */
  8. /**
  9.  * @param head The linked list's head.
  10.         Note that the head is guaranteed to be not null, so it contains at least one node.
  11.  * @param {ListNode} head
  12.  */
  13. var Solution = function(head) {
  14.   this.head = head
  15. };
  17. /**
  18.  * Returns a random node's value.
  19.  * @return {number}
  20.  */
  21. Solution.prototype.getRandom = function () {
  22.   let num = 0
  23.   let res = null
  24.   let head = this.head
  25.   while (head != null) {
  26.     num++
  27.     if (!Math.floor(Math.random() * num)) res = head.val
  28.     head = head.next
  29.   }
  30.   return res
  31. };
  33. /**
  34.  * Your Solution object will be instantiated and called as such:
  35.  * var obj = new Solution(head)
  36.  * var param_1 = obj.getRandom()
  37.  */

参考：
https://leetcode-cn.com/problems/linked-list-random-node/solution/xu-shui-chi-chou-yang-suan-fa-da-bai-hua-veal/
https://blog.csdn.net/anshuai_aw1/article/details/88750673