fengsehng

# 原文描述：

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;
}
}
``````

# 欢迎关注《IT面试题汇总》微信订阅号。每天推送经典面试题和面试心得技巧，都是干货！

## 微信订阅号二维码如下：

### fengsehng

LeetCode目录。

Leafage_M
2017/11/21
0
0
[LeetCode] Shuffle an Array 数组洗牌

Shuffle a set of numbers without duplicates. Example: // Init an array with set 1, 2, and 3.int[] nums = {1,2,3};Solution solution = new Solution(nums);// Shuffle the array [1,2......

2017/12/12
0
0

2017/12/29
17
0

rgvb178
2018/10/23
0
0

qq_32690999
2018/02/09
0
0

Garphy
40分钟前
6
0
MySQL 表崩溃修复

MySQL日志报错 2019-10-19 13:41:51 19916 [ERROR] /usr/local/mysql/bin/mysqld: Table './initread_hss/user_info' is marked as crashed and should be repaired2019-10-19 13:41:51 1......

50分钟前
6
0
Error和Exception

1.Error类和Exception类都是继承Throwable类 2.Error（错误）是系统中的错误，程序员是不能改变的和处理的，是在程序编译时出现的错误，只能通过修改程序才能修正。一般是指与虚拟机相关的问...

4
0
8086汇编基础 start 程序入口标签的示例

IDE : Masm for Windows 集成实验环境 2015     OS : Windows 10 x64 typesetting : Markdown    blog : my.oschina.net/zhichengjiu    gitee : gitee.com/zhichengjiu   ......

4
0
uni app 零基础小白到项目实战2

<template> <scroll-view v-for="(card, index) in list" :key="index"> <view v-for =(item, itemIndex) in card"> {{item.value}}</view> </scroll-view></template> GraceUi va......

6
0