382. Linked List Random Node(返回链表中随机一个节点的值)

太过爱你忘了你带给我的痛 2022-07-15 09:53 160阅读 0赞

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 returning.
    solution.getRandom();

题目大意：给定一个单链表，以同等的几率随机返回链表中一个节点的值。

题目思路：计算链表长度，再用随机数对该长度取余，返回该链表中次序等于该余数的节点的值。Follow up 中说明链表可能很长，我们不能提前知道链表长度，那么这里我们直接采取另一种思路，即著名的水塘抽样（Reservoir Sampling）问题。首先令int res = head.val，i=2；ListNode p = head.next，若p为空，则链表中只有一个节点，返回该节点值的概率为1。若p不为空，使用随机数产生1/i 的概率让res = p.val，并令i++，p = p.next，再继续判断p是否为空。可以计算出，这样对于链表中的每个节点，返回该节点值的几率都是一样的。代码如下：（119ms，beats 92.74%）

/**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) { val = x; }
     * }
     */
    public class Solution {
    
    
        private ListNode head;
    	    /** @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() {
    	        Random ran = new Random();
    	        int res = head.val,i = 2;
    	        ListNode p = head.next;
    	        while(p!=null){
    	        	if(ran.nextInt()%i==0)
    	        		res = p.val;
    	        	i++;
    	        	p = p.next;
    	        }
    	        return res;
    	    }
    }
    
    /**
     * Your Solution object will be instantiated and called as such:
     * Solution obj = new Solution(head);
     * int param_1 = obj.getRandom();
     */