JAVA:实现在给定的链表中找到一个随机节点算法(附完整源码)

package com.thealgorithms.datastructures.lists;
import java.util.ArrayList;
import java.util.List;
import java.util.Random;

public class RandomNode {
    private List<Integer> list;
    private int size;
    private static Random rand = new Random();

    static class ListNode {
        int val;
        ListNode next;

        ListNode(int val) {
            this.val = val;
        }
    }

    public RandomNode(ListNode head) {
        list = new ArrayList<>();
        ListNode temp = head;

        // Now using while loop to traverse through the linked list and
        // go on adding values and increasing the size value by 1
        while (temp != null) {
            list.add(temp.val);
            temp = temp.next;
            size++;
        }
    }

    public int getRandom() {
        int index = rand.nextInt(size);
        return list.get(index);
    }

    // Driver program to test above functions
    public static void main(String[] args) {
        ListNode head = new ListNode(15);
        head.next = new ListNode(25);
        head.next.next = new ListNode(4);
        head.next.next.next = new ListNode(1);
        head.next.next.next.next = new ListNode(78);
        head.next.next.next.next.next = new ListNode(63);
        RandomNode list = new RandomNode(head);
        int randomNum = list.getRandom();
        System.out.println("Random Node : " + randomNum);
    }
}




1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54