382.链表随机节点.md

382.链表随机节点

/*
 * @lc app=leetcode.cn id=382 lang=typescript
 *
 * [382] 链表随机节点
 */

// @lc code=start
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */

class Solution {
  constructor(head: ListNode | null) {}

  getRandom(): number {}
}

/**
 * Your Solution object will be instantiated and called as such:
 * var obj = new Solution(head)
 * var param_1 = obj.getRandom()
 */
// @lc code=end

使用数组

class Solution {
  nodes: ListNode[] = []
  constructor(head: ListNode | null) {
    while (head) {
      this.nodes.push(head)
      head = head.next
    }
  }

  getRandom(): number {
    return this.nodes[(Math.random() * this.nodes.length) >> 0].val
  }
}