382. Linked List Random Node

Given a singly linked list, return a random node’s value from the linked list. Each node must have the same probability of being chosen.

Follow up:
What if the linked list is extremely large and its length is unknown to you? Could you solve this efficiently without using extra space?

Example:

登录后复制

      
      

       
       // Init a singly linked list [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() should return either 1, 2, or 3 randomly. Each element should have equal probability of
      
      
      
      

       
       
1.
       
       
2.
       
       
3.
       
       
4.
       
       
5.
       
       
6.
       
       
7.
      
      

登录后复制

      
      

       
       /**
       
       
 * Definition for singly-linked list.
       
       
 * public class ListNode {
       
       
 *     int val;
       
       
 *     ListNode next;
       
       
 *     ListNode(int x) { val = x; }
       
       
 * }
       
       
 */
       
       
class Solution {
       
       

       
       
    /** @param
       
       
    private ListNode list=null;
       
       
    private int size=0;
       
       
    public Solution(ListNode head) {
       
       
        list=head;
       
       
        ListNode p=head;
       
       
        while(p!=null)
       
       
        {
       
       
            p=p.next;
       
       
            size++;
       
       
        }
       
       
    }
       
       

       
       
    /** Returns a random node's value. */
       
       
    public int getRandom() {
       
       
        ListNode ss=list;
       
       
        int rand=(int)(Math.random()*size);
       
       
        while(rand>0&&ss!=null)
       
       
        {
       
       
            ss=ss.next;
       
       
            rand--;
       
       
        }
       
       
        return ss!=null?ss.val:0;
       
       
    }
       
       
}
       
       

       
       
/**
       
       
 * Your Solution object will be instantiated and called as such:
       
       
 * Solution obj = new Solution(head);
       
       
 * int param_1 = obj.getRandom();
       
       
 */
      
      
      
      

       
       
1.
       
       
2.
       
       
3.
       
       
4.
       
       
5.
       
       
6.
       
       
7.
       
       
8.
       
       
9.
       
       
10.
       
       
11.
       
       
12.
       
       
13.
       
       
14.
       
       
15.
       
       
16.
       
       
17.
       
       
18.
       
       
19.
       
       
20.
       
       
21.
       
       
22.
       
       
23.
       
       
24.
       
       
25.
       
       
26.
       
       
27.
       
       
28.
       
       
29.
       
       
30.
       
       
31.
       
       
32.
       
       
33.
       
       
34.
       
       
35.
       
       
36.
       
       
37.
       
       
38.
       
       
39.
       
       
40.
       
       
41.