Linked List Random Node

Problem

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.

Implement the Solution class:

• Solution(ListNode head) Initializes the object with the head of the singly-linked list head.
• int getRandom() Chooses a node randomly from the list and returns its value. All the nodes of the list should be equally likely to be chosen.

Examples

Example 1:

graph LR;
1 --> 2 --> 3

Input
["Solution", "getRandom", "getRandom", "getRandom", "getRandom", "getRandom"]
[[[1, 2, 3]], [], [], [], [], [
Output
[null, 1, 3, 2, 2, 3]

Explanation
Solution solution = new Solution([1, 2, 3]);
solution.getRandom(); // return 1
solution.getRandom(); // return 3
solution.getRandom(); // return 2
solution.getRandom(); // return 2
solution.getRandom(); // return 3
// getRandom() should return either 1, 2, or 3 randomly. Each element should have equal probability of returning.

Constraints

• The number of nodes in the linked list will be in the range [1, 104].
• -104 <= Node.val <= 104
• At most 104 calls will be made to getRandom.

Solution

Method 1 - Using List Size

Use inbuilt random function to pickup the random value.

Code

Java

class Solution {
    private final ListNode head;
    private int size;

    public Solution(ListNode head) {
        this.head = head;
        size = 0;
        ListNode current = head;
        while (current != null) {
            current = current.next;
            size++;
        }
        this.size = size;

    }
    public int getRandom() {
        int randInt = (int)(Math.random() * size);
        ListNode curr = head;
        while (randInt > 0 && curr.next != null) {
            curr = curr.next;
            randInt--;
        }
        return curr.val;
    }
}

Complexity

• ⏰ Time complexity: O(n) for construction and O(n) for get random, where n is length of linked list
• 🧺 Space complexity: O(n) for storing n values in list

Method 4 - Using Reservoir Sampling and without Extra Space 🏆

We can use [Reservoir Sampling Explained](reservoir-sampling-explained) for k=1.

Read more about . Lets discuss how it applies here:

• lets says if the values are coming as 1, 2, 3 ..
• on 1 then we have 1 only choice to select : 1
• on 2 then out of two elements, we need to select 1, then new item should be given 1/2 chance
• so any random number that comes less than or equal to 1/2 then select : 2
• on 3 then out of three elements, we need to select 1, then new item should be given 1/3 chance, others will have 2/3 probability because they already exists with more probabilty
• so select : 3 if random number comes between 0 < random <= 1/3

Code

Java

Using Arraylist

public class Solution {
    private ListNode head;
    private Random rand;
    /** 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) {
            if (rand.nextInt(i) < k) {
                reservoir.set(rand.nextInt(k), node.val);
            }
            i++;
            node = node.next;
        }
        return reservoir.get(0);// or return reservoir when k > 1;
    }
}

Code Using Math.random()

class Solution {

	ListNode node;
	public Solution(ListNode head) {
		//store the head in node
		node = head;
	}

	public int getRandom() {
		//running index, i
		int count = 1;
		//our selection
		ListNode candidate = null;
		// curr assigned with the head of the node
		ListNode curr = node;
		//loop through all the nodes
		while (curr != null) {
			//pick random and check if the value is<or<= 1/i
			if (Math.random()<= 1.0 / count) {
				candidate = curr;
			}

			count += 1;
			curr = curr.next;
		}

		return candidate.val;
	}
}

Code Using rand.nextInt()

we can also use rand.nextInt() and count.

public class Solution {
    
    ListNode head;

    
    public Solution(ListNode h) {
        head = h;       
    }
    
	public int getRandom() {
		Random rand = new Random();
		int count = 0;
		ListNode curr = head;
		ListNode candidate = head;
		// traverse till end of list
		while (true) {
			if (curr == null) {
				break;
			}
			if (rand.nextInt(count + 1) == count) {
				candidate = curr;
			}
			curr = curr.next;
			count++;
		}
		return candidate.val;
	}
}