Question

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

Solution

  • Method 1: Use axtra space to get O(1). ```Java /**
    • Definition for singly-linked list.
    • public class ListNode {
    • int val;
    • ListNode next;
    • ListNode(int x) { val = x; }

    • } */ class Solution { private Random random; private HashMap<Integer, Integer> map; /** @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.map = new HashMap<>(); this.random = new Random(); ListNode cur = head; int count = 0; while(cur != null){ map.put(count++, cur.val); cur = cur.next; } }

      /** Returns a random node’s value. */ public int getRandom() { int rand = random.nextInt(map.size()); return map.get(rand); } }

    /**

    • Your Solution object will be instantiated and called as such:
    • Solution obj = new Solution(head);
    • int param_1 = obj.getRandom(); */ ```
  • Method 2: Reservoir Sampling ```Java /**
    • Definition for singly-linked list.
    • public class ListNode {
    • int val;
    • ListNode next;
    • ListNode(int x) { val = x; }

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

      /** Returns a random node’s value. */ public int getRandom() { ListNode cur = head.next; int count = 1; ListNode hold = head; while(cur != null){ count++; int rand = random.nextInt(count) + 1; if(rand == count) hold = cur; cur = cur.next; } return hold.val; } }

    /**

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