8000 select a random node from a linked list · developgo/algorithms_with_Go@9e93788 · GitHub
[go: up one dir, main page]
Skip to content
65ED

Commit 9e93788

Browse files
danruseidanrusei
committed
select a random node from a linked list
1 parent 931b8a5 commit 9e93788

File tree

3 files changed

+90
-1
lines changed

3 files changed

+90
-1
lines changed

‎README.md

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -35,7 +35,7 @@ WIP, the descriptions of the below `unsolved yet` problems can be found in the [
3535
- [] Union And Intersection Of 2 Linked Lists
3636
- [x] [Detect And Remove Loop In A Linked List](https://github.com/danrusei/algorithms_with_Go/tree/main/linkedlist/remove_loop)
3737
- [] Merge Sort For Linked Lists
38-
- [] Select A Random Node from A Singly Linked List
38+
- [x] [Select A Random Node from A Singly Linked List](https://github.com/danrusei/algorithms_with_Go/tree/main/linkedlist/random_node)
3939

4040
## [Dynamic Programming](https://github.com/danrusei/algorithms_with_Go/tree/main/dynamic)
4141

‎linkedlist/random_node/README.md

Lines changed: 33 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,33 @@
1+
# Select a Random Node from a Singly Linked List
2+
3+
Problem description: [GeeksforGeeks](https://www.geeksforgeeks.org/select-a-random-node-from-a-singly-linked-list/amp/)
4+
5+
Given a singly linked list, select a random node from linked list (the probability of picking a node should be 1/N if there are N nodes in list). You are given a random number generator.
6+
7+
## Algorithm
8+
9+
* initialize result as first node
10+
* initialize n = 2
11+
* traverse the linked list
12+
* generate a random number from 0 to n-1.
13+
* if the number is equal to 0, then replace result with current node.
14+
* n++
15+
16+
## Result
17+
18+
```bash
19+
$ go run main.go
20+
7
21+
$ go run main.go
22+
1
23+
$ go run main.go
24+
9
25+
$ go run main.go
26+
3
27+
$ go run main.go
28+
10
29+
$ go run main.go
30+
9
31+
$ go run main.go
32+
5
33+
```

‎linkedlist/random_node/main.go

Lines changed: 56 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,56 @@
1+
package main
2+
3+
import (
4+
"fmt"
5+
"math/rand"
6+
"time"
7+
8+
"github.com/danrusei/algorithms_with_go/linkedlist"
9+
)
10+
11+
type llist struct {
12+
linkedlist.Linkedlist
13+
}
14+
15+
// we can easily select a random node by using the length field of the linkedlist
16+
// let's assume this time that the length field has not been defined
17+
func (ll *llist) randomNode() int {
18+
if ll.Head == nil {
19+
return 0
20+
}
21+
22+
//NewSource returns a new pseudo-random Source seeded with the given value.
23+
r1 := rand.NewSource(time.Now().UnixNano())
24+
//New returns a new Rand that uses random values from x1 to generate other random values.
25+
r2 := rand.New(r1)
26+
27+
result := ll.Head.Val
28+
cur := ll.Head
29+
30+
// traverse the list and increase the n, which is the length of the yet discovered list
31+
n := 2
32+
for ; cur.Next != nil; cur = cur.Next {
33+
34+
if r2.Int()%n == 0 {
35+
result = cur.Val
36+
}
37+
n++
38+
}
39+
40+
return result
41+
}
42+
43+
func main() {
44+
list := llist{}
45+
list.AddAtEnd(5)
46+
list.AddAtEnd(8)
47+
list.AddAtEnd(10)
48+
list.AddAtEnd(3)
49+
list.AddAtEnd(1)
50+
list.AddAtEnd(9)
51+
list.AddAtEnd(7)
52+
list.AddAtEnd(2)
53+
54+
result := list.randomNode()
55+
fmt.Println(result)
56+
}

0 commit comments

Comments
 (0)
0