​LeetCode刷题实战382：链表随机节点

// 初始化一个单链表 [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();

import java.util.Random;
class Solution {
 
    private ListNode ls;
 
    /** @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) {
        ls=head;
    }
    
    /** Returns a random node's value. */
    public int getRandom() {
        ListNode tls=ls;
        Random rd=new Random(); //随机数随便，保证概率为1/i即可
        int i=1,rs=tls.val;
        while(tls!=null){
            if(rd.nextInt(i++)==0){
                rs=tls.val;
            }
            tls=tls.next;
        }
        return rs;
    }
}