?LeetCode刷題實(shí)戰(zhàn)382：鏈表隨機(jī)節(jié)點(diǎn)

// 初始化一個(gè)單鏈表 [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()方法應(yīng)隨機(jī)返回1,2,3中的一個(gè)，保證每個(gè)元素被返回的概率相等。
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(); //隨機(jī)數(shù)隨便，保證概率為1/i即可
        int i=1,rs=tls.val;
        while(tls!=null){
            if(rd.nextInt(i++)==0){
                rs=tls.val;
            }
            tls=tls.next;
        }
        return rs;
    }
}