[leetcode]-Linked List Random Node

谁借莪１个温暖的怀抱￠ 2022-09-25 09:19 24阅读 0赞

# 题目描述： #

给定一个单向的链表，要求以相等的概率返回

# 要求： #

时间复杂度o（n），空间复杂度o（1）

# 原文描述： #

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();

# 思路分析： #

*  因为链表的长度不固定，也没法通过下标取值，只能一边遍利，一边取值
 *  考虑在遍历时候，动态记录长度n，然后保证当前值的返回概率是1/n，我们以第2个数为例（就是head.next.val）选取的概率为(1/2)\* （2/3）*（3/4）* ………… (n-1) / n = 1/n （选取第2个数在长度为2的时候为1/2，其他的都不要选)而对于任意的第x数，由于可以覆盖前面的数，均有： (1/x) \* (x/(x+1)) \*…….(n-1) / n = 1/n
 *  第n个数就直接1/n
 *

# 代码： #

import java.util.Random;
    
    public class Solution {
    	 /** @param head The linked list's head.
        Note that the head is guaranteed to be not null, so it contains at least one node. */
    	ListNode head = null;
    	Random random = null;
    	public Solution(ListNode head) {
    		this.head = head;
    		random = new Random();
    	}
    
    	/** Returns a random node's value. */
    	public int getRandom() {
    		ListNode result = null;
    		ListNode current = head;
    		for(int n = 1;current != null;n++){
    			if(random.nextInt(n) == 0){
    				result = current;
    			}
    			current = current.next;
    		}
    		return result.val;
    	}
    }