fengsehng 发表于1年前
• 发表于 1年前
• 阅读 2
• 收藏 0
• 评论 0

# 原文描述：

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.

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].

// getRandom() should return either 1, 2, or 3 randomly. Each element should have equal probability of returning.
solution.getRandom();``````

# 思路分析：

• 因为链表的长度不固定，也没法通过下标取值，只能一边遍利，一边取值
• 考虑在遍历时候，动态记录长度n，然后保证当前值的返回概率是1/n，我们以第2个数为例（就是head.next.val）选取的概率为(1/2)* （2/3）（3/4） ……….. (n-1) / n = 1/n （选取第2个数在长度为2的时候为1/2，其他的都不要选)而对于任意的第x数，由于可以覆盖前面的数，均有： (1/x) * (x/(x+1)) *…….(n-1) / n = 1/n
• 第n个数就直接1/n
• -

# 代码：

``````import java.util.Random;

public class Solution {
/** @param head The linked list's head. Note that the head is guaranteed to be not null, so it contains at least one node. */
Random random = null;
random = new Random();
}

/** Returns a random node's value. */
public int getRandom() {
ListNode result = null;
for(int n = 1;current != null;n++){
if(random.nextInt(n) == 0){
result = current;
}
current = current.next;
}
return result.val;
}
}
``````

×