请你设计并实现一个满足 LRU 最近最少使用约束的数据结构。 实现 LRUCache 类： * LRUCache(int capacity)：以正整数作为容量 capacity 初始化 LRU 缓存 * int get(int key)：如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 * void put(int key, int value)：如果关键字 key 已经存在，则更新它的值；如果不存在，则插入这组 key-value 如果插入操作导致关键字数量超过 capacity，则应该逐出最久未使用的关键字。 get 和 put 必须以 O(1) 的平均时间复杂度运行。 示例： 输入：

给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random。 该指针可以指向链表中的任何节点，也可以指向空节点。 请构造这个链表的深拷贝。 深拷贝应该正好由 n 个全新节点组成，其中每个新节点的值都设为其对应原节点的值。 新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。 复制链表中的指针都不应该指向原链表中的节点。 例如，如果原链表中有 X 和 Y 两个节点，其中： X.random -> Y 那么在复制链表中对应的两个节点 x 和 y，也应该满足： x.random -> y 返回复制链表的头节点。 输入和输出中的链表用 n 个节点表示，每个节点用一个 [val, random_index] 表示： * val：表示