《零基础Go语言算法实战》【题目 4-6】随机选择单链表的一个节点并返回
《零基础Go语言算法实战》
【题目 4-6】随机选择单链表的一个节点并返回
给定一个单链表，请随机选择链表的一个节点，并返回相应的节点值。保证每个节点被
选择的概率相同。
【解答】
① 思路。
通过 rand.Float64() 函数可以返回 [0,1) 范围内的随机数，利用这个函数完成随机化选择
节点的过程。
② Go 语言实现。
package main
import (
"fmt"
"math/rand"
)
// 定义单链表
type ListNode struct {
Data int
Next *ListNode
}
type Head struct {
head *ListNode
}
// 初始化链表
func NewListNode(head *ListNode) Head {
return Head{head: head}
}
// 返回随机节点的值
func (h *Head) GetRandom() int {
scope, selectPoint, curr := 1, 0, h.head
for curr != nil {
if rand.Float64() < 1.0/float64(scope) {
selectPoint = curr.Data
}
scope += 1
curr = curr.Next
}
return selectPoint
}
func main() {
nodeList := ListNode{6, nil}
head := NewListNode(&nodeList)
obj := NewListNode(head.head)
ret := obj.GetRandom()
fmt.Println(ret)
}