[leetcode]382. Linked List Random Node

以你之姓@ 2022-09-25 08:17 26阅读 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();

问题描述：给定一个链表，在链表长度未知的情况下，如何以均等概率得到链表中的一个结点的值。

分析：这是所谓的[蓄水池抽样问题][Link 1]。这个方法很巧妙。

/**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) { val = x; }
     * }
     */
    public class Solution {
        ListNode myhead = null;
        /** @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.myhead = head;
        }
        
        /** Returns a random node's value. */
        public int getRandom() {
            int n = 0, res = this.myhead.val;
            ListNode p = this.myhead;
            while(p != null){
                n++;
                int genRan = new Random().nextInt(n) + 1;
                if(n == genRan){
                    res = p.val;
                }
                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();
     */

[Link 1]: http://http://www.cnblogs.com/HappyAngel/archive/2011/02/07/1949762.html