Solution URL
https://leetcode.com/submissions/detail/414924624/
代码
/**
* Definition for singly-linked list.
* 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; }
* }
*/
class Solution {
//ans: https://leetcode-cn.com/problems/linked-list-random-node/solution/lc-382-lian-biao-sui-ji-jie-dian-wo-gan-jio-jiang-/
ListNode head;
Random r = new Random();
/** @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) {
this.head = head;
}
/** Returns a random node's value. */
public int getRandom() {
if(head == null) return -1;
ListNode cur = head;
int val = cur.val;
cur = cur.next;
int i = 1;
while(cur != null){
i++;
if(r.nextInt(i) == 0){
val = cur.val;
}
cur = cur.next;
}
return val;
}
}
/**
* Your Solution object will be instantiated and called as such:
* Solution obj = new Solution(head);
* int param_1 = obj.getRandom();
*/
