LeetCode题练习与总结：链表随机节点--382

一、题目描述

给你一个单链表，随机选择链表的一个节点，并返回相应的节点值。每个节点 被选中的概率一样 。

实现 Solution 类：

Solution(ListNode head) 使用整数数组初始化对象。
int getRandom() 从链表中随机选择一个节点并返回该节点的值。链表中所有节点被选中的概率相等。

示例：

输入
["Solution", "getRandom", "getRandom", "getRandom", "getRandom", "getRandom"]
[[[1, 2, 3]], [], [], [], [], []]
输出
[null, 1, 3, 2, 2, 3]解释
Solution solution = new Solution([1, 2, 3]);
solution.getRandom(); // 返回 1
solution.getRandom(); // 返回 3
solution.getRandom(); // 返回 2
solution.getRandom(); // 返回 2
solution.getRandom(); // 返回 3
// getRandom() 方法应随机返回 1、2、3中的一个，每个元素被返回的概率相等。

提示：

链表中的节点数在范围 [1, 10^4] 内
-10^4 <= Node.val <= 10^4
至多调用 getRandom 方法 10^4 次

二、解题思路

初始化：首先，我们需要一个ListNode类来表示链表的节点，并且需要实现一个deserialize方法来将输入的字符串转换为链表。ListNode类包含一个整数值val和一个指向下一个节点的引用next。
反序列化：deserialize方法将输入的字符串（形如"[1,2,3]"）转换成链表。这个方法首先创建一个哑节点dummy，然后遍历字符串中的每个值，创建新的ListNode并将其添加到链表中。最后，返回哑节点的下一个节点，即链表的头节点。
Solution类：Solution类负责实现随机选择链表节点的功能。它包含一个构造函数，接受链表的头节点，并初始化一个Random对象用于生成随机数。
随机选择节点：getRandom方法是Solution类中的关键方法。它遍历链表，使用水塘抽样算法（Reservoir Sampling）来随机选择一个节点。在遍历过程中，每个节点都有相同的概率被选中。具体来说，遍历到第i个节点时，我们以1/i的概率决定是否选择当前节点。如果决定选择当前节点，我们就更新结果result为当前节点的值。
主方法：在Main类的main方法中，我们首先使用ListNode.deserialize方法将字符串转换为链表。然后，我们创建一个Solution对象，并多次调用getRandom方法来模拟随机选择节点值的过程。

三、具体代码

import java.util.Random;class ListNode {int val;ListNode next;ListNode(int x) { val = x; }// 反序列化方法，将字符串转换为链表public static ListNode deserialize(String data) {if (data.isEmpty()) return null;String[] values = data.substring(1, data.length() - 1).split(",");ListNode dummy = new ListNode(0);ListNode current = dummy;for (String value : values) {current.next = new ListNode(Integer.parseInt(value));current = current.next;}return dummy.next;}
}class Solution {ListNode head;Random random;public Solution(ListNode head) {this.head = head;this.random = new Random();}public int getRandom() {ListNode current = head;int result = head.val;int i = 1;while (current != null) {if (random.nextInt(i) == 0) {result = current.val;}current = current.next;i++;}return result;}
}public class Main {public static void main(String[] args) {// 反序列化链表ListNode head = ListNode.deserialize("[1,2,3]");// 创建Solution对象Solution solution = new Solution(head);// 模拟多次调用getRandom方法System.out.println(solution.getRandom());System.out.println(solution.getRandom());System.out.println(solution.getRandom());System.out.println(solution.getRandom());System.out.println(solution.getRandom());}
}

四、时间复杂度和空间复杂度

1. 时间复杂度

ListNode.deserialize 方法：
- 时间复杂度：O(n)，其中 n 是输入字符串中数字的数量。这个方法遍历了字符串中的所有数字，每个数字都进行了一次解析操作。
Solution.getRandom 方法：
- 时间复杂度：O(m)，其中 m 是链表的长度。每次调用 getRandom 方法都需要遍历整个链表。
Main.main 方法：
- 时间复杂度：O(1) + O(m) + O(k * m)，其中 m 是链表的长度，k 是调用 getRandom 方法的次数。ListNode.deserialize 方法调用一次，所以是 O(1)，然后创建 Solution 对象也是 O(1)，接下来调用 getRandom 方法 k 次，每次是 O(m)。

综合上述分析，整体时间复杂度是：

反序列化链表：O(n)
创建 Solution 对象：O(1)
调用 getRandom 方法 k 次：O(k * m)

如果 n 是链表的长度，那么反序列化链表的时间复杂度可以视为 O(m)，因此整体时间复杂度是 O(m + k * m) = O((k + 1) * m)。

2. 空间复杂度

ListNode.deserialize 方法：
- 空间复杂度：O(m)，其中 m 是链表的长度。这个方法创建了 m 个 ListNode 对象。
Solution 类：
- 空间复杂度：O(1)，Solution 类只存储了链表的头节点和一个 Random 对象。
Main.main 方法：
- 空间复杂度：O(1)，除了链表本身外，main 方法没有使用额外的空间。

综合上述分析，整体空间复杂度是：

反序列化链表：O(m)
创建 Solution 对象：O(1)
调用 getRandom 方法：O(1)

因此，整体空间复杂度是 O(m)，即链表长度。

五、总结知识点

Java 类定义：
- ListNode 和 Solution 类的定义，以及它们各自的构造方法。
链表操作：
- 链表的创建和遍历。
- 使用 ListNode 类创建链表节点，并链接它们形成链表。
字符串处理：
- 使用 substring 方法截取字符串。
- 使用 split 方法按特定字符分割字符串。
数字解析：
- 使用 Integer.parseInt 方法将字符串转换为整数。
动态内存分配：
- 在 deserialize 方法中动态创建链表节点。
伪随机数生成：
- 使用 Random 类生成伪随机数。
概率算法：
- 在 getRandom 方法中，使用了一个著名的概率算法，称为“水塘抽样”（Reservoir Sampling），以等概率从链表中随机选择一个节点。
循环和递增：
- 在 getRandom 方法中使用 while 循环遍历链表，并使用变量 i 来记录遍历的节点数量。
设计模式：
- 使用了“哑节点”（dummy node）设计模式在 deserialize 方法中简化链表节点的添加操作。