Given a singly linked list, return a random node’s value from the linked list. Each node must have the same probability of being chosen.
Follow up: What if the linked list is extremely large and its length is unknown to you? Could you solve this efficiently without using extra space?
Example:
// Init a singly linked list [1,2,3]. ListNode head = new ListNode(1); head.next = new ListNode(2); head.next.next = new ListNode(3); Solution solution = new Solution(head);
// getRandom() should return either 1, 2, or 3 randomly. Each element should have equal probability of returning. solution.getRandom();
首先需要了解一下蓄水池抽样。 简单介绍一下蓄水池抽样：
题目背景： “给出一个数据流，这个数据流的长度很大或者未知。并且对该数据流中数据只能访问一次。请写出一个随机选择算法，使得数据流中所有数据被选中的概率相等。”
第一种情况：数据流长度为1，则这个元素被选中概率是1/1；
第二种情况：数据流长度为2，当读取到1元素的时候，数据流并没有结束，所以不能直接返回1，读取到第二个的时候，数据流结束了，因此我们生成一个0到1的随机数R,如果R小于0.5我们就返回第一个数据，如果R大于0.5，返回第二个数据。
第三种情况：我们陆续收到了数据1、2和前面的例子一样，我们只能保存一个数据，所以必须淘汰1和2中的一个。应该如何淘汰呢？不妨和上面例子一样，我们按照二分之一的概率淘汰一个，例如我们淘汰了2。继续读取流中的数据3，发现数据流结束了，我们知道在长度为3的数据流中，如果返回数据3的概率为1/3,那么才有可能保证选择的正确性。也就是说，目前我们手里有1,3两个数据，我们通过一次随机选择，以1/3的概率留下数据3，以2/3的概率留下数据1.那么数据1被最终留下的概率是多少呢？
数据1被留下：（1/2）*(2/3) = 1/3 数据2被留下概率：（1/2）*(2/3) = 1/3 数据3被留下概率：1/3
因此，这个方法满足题目要求。
这道题用到的就是这个蓄水池算法。看代码的时候就简单多了。
ListNode head; public Solution(ListNode head) { this.head = head; } public int getRandom() { Random random = new Random(); int result = head.val; ListNode currNode = head; for(int i=1; currNode.next!=null; i++) { currNode = currNode.next; if((random.nextInt(i + 1)) == i) { result = currNode.val; } } return result; }