题目

类型：链表
image.png

解题思路

链表长度只有 链表随机节点 - 图2 ，因此可以在初始化时遍历整条链表，将所有的链表值预处理到一个数组内。
在查询时随机一个下标，并将数组中对应下标内容返回出去。

代码

  1. /**
  2.  * Definition for singly-linked list.
  3.  * public class ListNode {
  4.  *     int val;
  5.  *     ListNode next;
  6.  *     ListNode() {}
  7.  *     ListNode(int val) { this.val = val; }
  8.  *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  9.  * }
  10.  */
  11. class Solution {
  12.     ListNode head;
  13.     Random random = new Random(20220116);
  14.     public Solution(ListNode _head) {
  15.         head = _head;
  16.     }
  17.     public int getRandom() {
  18.         int ans = 0, idx = 0;
  19.         ListNode t = head;
  20.         while (t != null && ++idx >= 0) {
  21.             if (random.nextInt(idx) == 0) ans = t.val;
  22.             t = t.next;
  23.         }
  24.         return ans;
  25.     }
  26. }
  27. /**
  28.  * Your Solution object will be instantiated and called as such:
  29.  * Solution obj = new Solution(head);
  30.  * int param_1 = obj.getRandom();
  31.  */