|
| 1 | +/** Author : Suraj Kumar |
| 2 | + * Github : https://github.com/skmodi649 |
| 3 | + */ |
| 4 | + |
| 5 | +/** PROBLEM DESCRIPTION : |
| 6 | + * There is a single linked list and we are supposed to find a random node in the given linked list |
| 7 | + */ |
| 8 | + |
| 9 | +/** ALGORITHM : |
| 10 | + * Step 1 : START |
| 11 | + * Step 2 : Create an arraylist of type integer |
| 12 | + * Step 3 : Declare an integer type variable for size and linked list type for head |
| 13 | + * Step 4 : We will use two methods, one for traversing through the linked list using while loop and also increase the size by 1 |
| 14 | + * |
| 15 | + * (a) RandomNode(head) |
| 16 | + * (b) run a while loop till null; |
| 17 | + * (c) add the value to arraylist; |
| 18 | + * (d) increase the size; |
| 19 | + * |
| 20 | + * Step 5 : Now use another method for getting random values using Math.random() and return the value present in arraylist for the calculated index |
| 21 | + * 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 |
| 22 | + * Step 7 : STOP |
| 23 | + */ |
| 24 | + |
| 25 | + |
| 26 | +packagecom.thealgorithms.datastructures.lists; |
| 27 | + |
| 28 | +importjava.util.ArrayList; |
| 29 | +importjava.util.List; |
| 30 | +importjava.util.Random; |
| 31 | + |
| 32 | +publicclassRandomNode { |
| 33 | +privateList<Integer>list; |
| 34 | +privateintsize; |
| 35 | +privatestaticRandomrand =newRandom(); |
| 36 | + |
| 37 | +staticclassListNode { |
| 38 | +intval; |
| 39 | +ListNodenext; |
| 40 | + |
| 41 | +ListNode(intval) { |
| 42 | +this.val =val; |
| 43 | + } |
| 44 | + } |
| 45 | + |
| 46 | +publicRandomNode(ListNodehead) { |
| 47 | +list =newArrayList<>(); |
| 48 | +ListNodetemp =head; |
| 49 | + |
| 50 | +// Now using while loop to traverse through the linked list and |
| 51 | +// go on adding values and increasing the size value by 1 |
| 52 | +while (temp !=null) { |
| 53 | +list.add(temp.val); |
| 54 | +temp =temp.next; |
| 55 | +size++; |
| 56 | + } |
| 57 | + } |
| 58 | + |
| 59 | +publicintgetRandom() { |
| 60 | +intindex =rand.nextInt(size); |
| 61 | +returnlist.get(index); |
| 62 | + } |
| 63 | + |
| 64 | +// Driver program to test above functions |
| 65 | +publicstaticvoidmain(String[]args) { |
| 66 | +ListNodehead =newListNode(15); |
| 67 | +head.next =newListNode(25); |
| 68 | +head.next.next =newListNode(4); |
| 69 | +head.next.next.next =newListNode(1); |
| 70 | +head.next.next.next.next =newListNode(78); |
| 71 | +head.next.next.next.next.next =newListNode(63); |
| 72 | +RandomNodelist =newRandomNode(head); |
| 73 | +intrandomNum =list.getRandom(); |
| 74 | +System.out.println("Random Node : " +randomNum); |
| 75 | + } |
| 76 | +} |
| 77 | + |
| 78 | + |
| 79 | +/** |
| 80 | + * OUTPUT : |
| 81 | + * First output : |
| 82 | + * Random Node : 25 |
| 83 | + * Second output : |
| 84 | + * Random Node : 78 |
| 85 | + * Time Complexity : O(n) |
| 86 | + * Auxiliary Space Complexity : O(1) |
| 87 | + * Time Complexity : O(n) |
| 88 | + * Auxiliary Space Complexity : O(1) |
| 89 | + */ |
| 90 | + |
| 91 | +/** Time Complexity : O(n) |
| 92 | + * Auxiliary Space Complexity : O(1) |
| 93 | + */ |