🥈

Linked List Random Node

Created

2022/01/07 04:01

문제 번호

382

카테고리

Linked List

Math

Reservoir Sampling

Randomized

Linked List Random Node - LeetCode

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 integer array nums. int getRandom() Chooses a node randomly from the list and returns its value.

https://leetcode.com/problems/linked-list-random-node/

Code

제출 날짜	시간	메모리
2021/01/07	12 ms	7.5 MB

// 382. Linked List Random Node
//
// https://leetcode.com/problems/linked-list-random-node/

// math/rand package has been used to call Intn.
import (
	"math/rand"
)

// Definition for singly-linked list.
// type ListNode struct {
//     Val int
//     Next *ListNode
// }

// Solution has the length of input list, and its contents.
type Solution struct {
	length  int
	content []int
}

// Constructor function initialize the Solution structure with the given list.
func Constructor(head *ListNode) Solution {
	sol := Solution{}
	for head != nil {
		sol.length++
		sol.content = append(sol.content, head.Val)
		head = head.Next
	}
	return sol
}

// GetRandom function returns the value of the random index node.
// This is done by calling rand package funciton.
// A index range is the length which is held by Solution structure.
// Solution structure already knows the content of the each index, that is the answer.
func (this *Solution) GetRandom() int {
	index := rand.Intn(this.length)
	return this.content[index]
}

// Your Solution object will be instantiated and called as such:
// obj := Constructor(head);
// param_1 := obj.GetRandom();
Go
복사