力扣382.链表随机节点（java利用数组随机返回节点值）

本文主要是介绍力扣382.链表随机节点（java利用数组随机返回节点值），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Problem: 382. 链表随机节点

思路

注意链表与数组的特性，对于随机访问读取的操作利用数组可以较方便实现，所以我们可以将链表中的节点值先存入到数组中最后再取出随机生成节点位置的值。

解题方法

1.生成List集合与Random对象并在构造器中完成对其的初始化。
2.将链表的节点值存入到List集合中
3.随机返回一个节点值

复杂度

• 时间复杂度:

$O(n)$

• 空间复杂度:

$O(n)$

Code

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {//Time Complexity: O(N)//Space Complexity: O(N)List<Integer> list;Random random;public Solution(ListNode head) {ListNode p = head;list = new ArrayList<>();//将节点都添加到list集合while (p != null) {list.add(p.val);p = p.next;}random = new Random();}public int getRandom() {return list.get(random.nextInt(list.size()));}
}/*** Your Solution object will be instantiated and called as such:* Solution obj = new Solution(head);* int param_1 = obj.getRandom();*/

这篇关于力扣382.链表随机节点（java利用数组随机返回节点值）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---