LeetCode例题：
给定一个单链表，随机选择链表的一个节点，并返回相应的节点值。保证每个节点被选的概率一样。
进阶:
如果链表十分大且长度未知，如何解决这个问题？你能否使用常数级空间复杂度实现？
示例:
// 初始化一个单链表 [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();
网址:https://leetcode-cn.com/problems/linked-list-random-node/
链表结构类
public class ListNode {
int val;
ListNode next;
ListNode() {}
ListNode(int val) { this.val = val; }
ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
测试&&方法类
import java.util.Random; public class LeetCode { public ListNode listNode; LeetCode(ListNode listNode) { this.listNode = listNode; } int getRandom() { int i = 2;
Random random = new Random(); int rand = this.listNode.val; ListNode listNode = this.listNode.next; while (null != listNode) { if (random.nextInt(i) == 0) { rand = listNode.val; } i++; listNode = listNode.next; } return rand; } public static void main(String[] args) { ListNode head = new ListNode(1); head.next = new ListNode(2); head.next.next = new ListNode(3); LeetCode leetCode = new LeetCode(head); System.out.println(leetCode.getRandom()); } }
原理是
链表元素只有一个时候 不会进入if，所以第一个概率是1/n(n=1)
当为2个的时候，进入if,随机数会在0,1之间生成，所以每一个概率是1/n
当为3个的时候，进入2次if,想要方法返回第一个,第一次进if的时候必须是随机到1，概率为1/2，第二次进入if时候，必须随机到1或者2，概率是2/3，然后相乘 1/2 * 2/3 = 1/3（1/n）
其他以此类推 每个元素的概率都是1/n，这样的时间复杂度是O（n）只遍历一次，就可以取出链表中的元素，如果按照先遍历列表，再随机到数后再去遍历会导致遍历两次，且时间复杂度最坏情况是O（n^2）