题目
给你一个单链表，随机选择链表的一个节点，并返回相应的节点值。每个节点 被选中的概率一样 。
实现 Solution 类：
Solution(ListNode head) 使用整数数组初始化对象。
int getRandom() 从链表中随机选择一个节点并返回该节点的值。链表中所有节点被选中的概率相等。
示例：
输入
[“Solution”, “getRandom”, “getRandom”, “getRandom”, “getRandom”, “getRandom”]
[[[1, 2, 3]], [], [], [], [], []]
输出
[null, 1, 3, 2, 2, 3]
解释
Solution solution = new Solution([1, 2, 3]);
solution.getRandom(); // 返回 1
solution.getRandom(); // 返回 3
solution.getRandom(); // 返回 2
solution.getRandom(); // 返回 2
solution.getRandom(); // 返回 3
// getRandom() 方法应随机返回 1、2、3中的一个，每个元素被返回的概率相等。
提示：
链表中的节点数在范围 [1, 104] 内
-104 <= Node.val <= 104
至多调用 getRandom 方法 104 次
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/linked-list-random-node
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
解决方法
class Solution(head: ListNode?) {
private var mHead:ListNode? = head
fun getRandom(): Int {
var result = -1
var i = 1
var node = mHead
while (node != null) {
if (Random().nextInt(i++) == 0){
result = node.`val`
}
node = node.next
}
return result
}
}
解决思路
从链表头开始，遍历整个链表，对遍历到的第 i 个节点，使用Random类,随机选择区间 [0,i) 内的一个整数，如果其等于 0，则将答案置为该节点值，否则答案不变。该算法会保证每个节点的值成为最后被返回的值的概率均为1/n.(定义一个变量result，用于存放结果，第一个节点一定为0(Random.nextInt(1))，所以第一个数首先会放到一个变量里,后续在遍历的过程中，如果有返回0的情况,那就替换result的值即可)
https://www.cnblogs.com/snowInPluto/p/5996269.html
总结
该算法当时看了半天题解也没有看懂
建议先看解决方法 在看解决思路
