382. Linked List Random Node.md

382. Linked List Random Node

---

leetcode Daily Challenge on December 2nd, 2020.

---

Difficulty : Medium

Related Topics : Reservoir Sampling

---

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

• mine
  • Java
    • Runtime: 13 ms, faster than 47.33%, Memory Usage: 40.8 MB, less than 75.52% of Java online submissions

      //O(N)time
      //O(N)space
      private List<Integer> list;
      
      public Solution(ListNode head) {
          list = new ArrayList<>();
          while (head != null) {
              list.add(head.val);
              head = head.next;
          }
      }
      
      public int getRandom() {
          int index = (int)(Math.random() * list.size());
          return list.get(index);
      }
      

---

• the most votes

• Reservoir Sampling Runtime: 16 ms, faster than 14.27%, Memory Usage: 40.4 MB, less than 97.91% of Java online submissions

  // O(n)time
  // O(1)space
  private ListNode head;
  
  public Solution(ListNode head) {
      this.head = head;
  }
  
  public int getRandom() {
      int scope = 1, chosenValue = 0;
      ListNode curr = this.head;
      while (curr != null) {
          if (Math.random() < 1.0 / scope) chosenValue = curr.val;
          scope += 1;
          curr = curr.next;
      }
      return chosenValue;
  }
  

---