Linked List Random Node

Reservoir Sampling

Medium

Given a singly linked list, return a random node's value from the linked list. Each node must have thesame probabilityof 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();

Solution

Reservoir Sampling

O(1) space, O(n) time

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    private Random rand;
    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;
        rand = new Random();
    }

    /** Returns a random node's value. */
    public int getRandom() {
        int result = -1;
        ListNode p = head;
        int count = 0;

        while (p != null) {
            count++;
            if (rand.nextInt(count) < 1) {
                result = p.val;
            }
            p = p.next;
        }
        return result;
    }
}

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

A more generic one for k > 1 reservoir sampling

public class Solution {
    private ListNode head;
    private Random rand;
    /** @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;
        this.rand = new Random();
    }

    /** Returns a random node's value. */
    public int getRandom() {
        int k = 1;
        ListNode node = this.head;
        int res = node.val;
        int i = 0;
        ArrayList<Integer> reservoir = new ArrayList<Integer>();

        while (i < k && node != null) {
            reservoir.add(node.val);
            node = node.next;
            i++;
        }
        i++; // i == k  =>  i == k+1
        while (node != null) {
            int j = rand.nextInt(i);
            if (j < k) {
                reservoir.set(j, node.val);
            }
            i++;
            node = node.next;
        }
        return reservoir.get(0);// or return reservoir when k > 1;
    }
}

以上的方案都需要每次getRandom()时遍历全部的list，不甚高效。

Random of the index number itself

初始化时就得到总长度length，在getRandom()时再随机一个index，作为要取的index，遍历list到那个index取出值返回。

这个在best case会比reservoir sampling更快，因为有可能第一个就返回了。但是在OJ中实测没有明显区别。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
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. */
    public Solution(ListNode head) {
        root = head;
        int count = 0;
        ListNode p = root;
        while (p != null)
        {
            p = p.next;
            count++;
        }
        length = count;
    }

    /** Returns a random node's value. */
    public int getRandom() {
        Random rand = new Random();
        int n = rand.nextInt(length);
        ListNode p = root;
        while (n-- > 0)
        {
            p = p.next;
        }
        return p.val;
    }

    private int length;
    private ListNode root;
}

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

Reference

https://leetcode.com/problems/linked-list-random-node/discuss/85659/Brief-explanation-for-Reservoir-Sampling