|
| 1 | +packagemedium; |
| 2 | + |
| 3 | +importjava.util.HashMap; |
| 4 | +importjava.util.Map; |
| 5 | +importjava.util.Random; |
| 6 | + |
| 7 | +importclasses.ListNode; |
| 8 | + |
| 9 | +/**382. Linked List Random Node QuestionEditorial Solution My Submissions |
| 10 | +Total Accepted: 43 |
| 11 | +Total Submissions: 147 |
| 12 | +Difficulty: Medium |
| 13 | +Given a singly linked list, return a random node's value from the linked list. Each node must have the same probability of being chosen. |
| 14 | +
|
| 15 | +Follow up: |
| 16 | +What if the linked list is extremely large and its length is unknown to you? Could you solve this efficiently without using extra space? |
| 17 | +
|
| 18 | +Example: |
| 19 | +
|
| 20 | +// Init a singly linked list [1,2,3]. |
| 21 | +ListNode head = new ListNode(1); |
| 22 | +head.next = new ListNode(2); |
| 23 | +head.next.next = new ListNode(3); |
| 24 | +Solution solution = new Solution(head); |
| 25 | +
|
| 26 | +// getRandom() should return either 1, 2, or 3 randomly. Each element should have equal probability of returning. |
| 27 | +solution.getRandom(); |
| 28 | +*/ |
| 29 | +publicclassLinkedListRandomNode { |
| 30 | + |
| 31 | +} |
| 32 | + |
| 33 | +classSolution { |
| 34 | +privateMap<Integer,ListNode>map; |
| 35 | +privateRandomrand; |
| 36 | + |
| 37 | +/** @param head The linked list's head. Note that the head is guanranteed to be not null, so it contains at least one node. */ |
| 38 | +publicSolution(ListNodehead) { |
| 39 | +map =newHashMap(); |
| 40 | +rand =newRandom(); |
| 41 | +inti =0; |
| 42 | +while(head !=null){ |
| 43 | +map.put(i++,head); |
| 44 | +head =head.next; |
| 45 | + } |
| 46 | + } |
| 47 | + |
| 48 | +/** Returns a random node's value. */ |
| 49 | +publicintgetRandom() { |
| 50 | +returnmap.get(rand.nextInt(map.size())).val; |
| 51 | + } |
| 52 | +} |
| 53 | + |