题目
给定一个单链表，随机选择链表的一个节点，并返回相应的节点值。保证每个节点被选的概率一样。
进阶:
如果链表十分大且长度未知，如何解决这个问题？你能否使用常数级空间复杂度实现？
示例:
// 初始化一个单链表 [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()方法应随机返回1,2,3中的一个，保证每个元素被返回的概率相等。
solution.getRandom();
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/linked-list-random-node
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
答案分析
先算出长度，再用长度取随机数。
我的答案：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
private ListNode head;
private int length;
/** @param head The linked list's head.
Note that the head is guaranteed to be not null, so it contains at least one node. */
public Solution(ListNode head) {
this.head = head;
this.length = 0;
ListNode p = head;
while (p != null) {
length++;
p = p.next;
}
}
/** Returns a random node's value. */
public int getRandom() {
Random r = new Random();
int index = r.nextInt(this.length);
int count = 0;
ListNode p = this.head;
while (p != null) {
if (count == index) {
return p.val;
}
count++;
p = p.next;
}
return -1;
}
}
/**
* Your Solution object will be instantiated and called as such:
* Solution obj = new Solution(head);
* int param_1 = obj.getRandom();
*/
执行用时：15 ms
别人的答案：
利用蓄水池采样原理，无需事先计算list长度即可求解，具体代码如下:
public class Solution {
Random r;
ListNode head;
public Solution(ListNode head) {
this.r = new Random();
this.head = head;
}
public int getRandom() {
int count = 1;
ListNode nodeVal = head;
ListNode curr = head;
while (curr != null) {
if (r.nextInt(count++) == 0) {
nodeVal = curr;
}
curr = curr.next;
}
return nodeVal.val;
}
}