package com.thealgorithms.datastructures.lists;

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

/**
 * @author <a href="https://github.com/skmodi649">Suraj Kumar</a>
 * <p>
 * PROBLEM DESCRIPTION :
 * There is a single linked list and we are supposed to find a random node in the given linked list
 * <p>
 * ALGORITHM :
 * Step 1 : START
 * Step 2 : Create an arraylist of type integer
 * Step 3 : Declare an integer type variable for size and linked list type for head
 * Step 4 : We will use two methods, one for traversing through the linked list using while loop and
 * also increase the size by 1
 * <p>
 * (a) RandomNode(head)
 * (b) run a while loop till null;
 * (c) add the value to arraylist;
 * (d) increase the size;
 * <p>
 * Step 5 : Now use another method for getting random values using Math.random() and return the
 * value present in arraylist for the calculated index Step 6 : Now in main() method we will simply
 * insert nodes in the linked list and then call the appropriate method and then print the random
 * node generated Step 7 : STOP
 */
public class RandomNode {

    private final List<Integer> list;
    private int size;
    private static final 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);
    }

    /**
     * OUTPUT :
     * First output :
     * Random Node : 25
     * Second output :
     * Random Node : 78
     * Time Complexity : O(n)
     * Auxiliary Space Complexity : O(1)
     * Time Complexity : O(n)
     * Auxiliary Space Complexity : O(1)
     * Time Complexity : O(n)
     * Auxiliary Space Complexity : O(1)
     */
    // 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);
    }
}