链表随机节点

382. 链表随机节点

给你一个单链表，随机选择链表的一个节点，并返回相应的节点值。每个节点被选中的概率一样。

示例 1:

Solution solution = new Solution([1, 2, 3]);
solution.getRandom(); // 返回 1
solution.getRandom(); // 返回 3
solution.getRandom(); // 返回 2
solution.getRandom(); // 返回 2
solution.getRandom(); // 返回 3
// getRandom() 方法应随机返回 1、2、3 中的一个，每个元素被返回的概率相等。

代码

思路：

声明 ListNode 节点函数
链表初始化
- 根据数组arr.length创建链表
  - 因为头节点有可能发生变化：使用虚拟头节点可以避免复杂的分类讨论
  - 头节点
  - 长度
- while 中注意：结束要更新到下一个
- 赋予真实头节点
链表随机方法
- 声明最大值为链表长度，最小值为 1
- 随机数公式：parseInt(Math.random()*(maxNum-minNum+1)+minNum,10)
- 根据随机数下标返回节点

class ListNode {
  constructor(val,next){
    this.val = val
    this.next = next ||  null
  }
}

var Solution = function(arr) {
  let dummyNode = new ListNode(-1)
  let current = dummyNode

  this.head = null
  this.size = 0


  while(arr.length){
    let val = arr.shift()

    let node = new ListNode(val)
    current.next = node
    current = current.next // // 结束要更新到下一个

    this.size ++
  }

  this.head =  dummyNode.next
};


Solution.prototype.getRandom = function() {
  let maxNum = this.size
  let minNum = 1
  const index = parseInt(Math.random()*(maxNum-minNum+1)+minNum,10)

  let node = this.head
  for(let i=0;i<index-1;i++){
    node = node.next
  }
  return node
};

var arr = [1,2,3]
const nodeList = new Solution(arr)

console.log(nodeList.getRandom())

382. 链表随机节点​

代码​

382. 链表随机节点

代码