86. 分隔链表

给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。

你应当 保留 两个分区中每个节点的初始相对位置。

示例 1：

输入：head = [1,4,3,2,5,2], x = 3
输出：[1,2,2,4,3,5]

示例 2：

输入：head = [2,1], x = 2
输出：[1,2]

提示：

• 链表中节点的数目在范围 [0, 200] 内
• -100 <= Node.val <= 100
• -200 <= x <= 200

class Solution {
    public ListNode partition(ListNode head, int x) {
        ListNode small = new ListNode(0);
        ListNode curSmall = small;
        ListNode big = new ListNode(0);
        ListNode curBig = big;
        while (head != null) {
            if (head.val < x) {
                small.next = head;
                small = small.next;
            } else {
                big.next = head;
                big = big.next;
            }
            head = head.next;
        }
        big.next = null;
        small.next = curBig.next;
        return curSmall.next;
    }
}

1. ListNode small = new ListNode(0); 和 ListNode big = new ListNode(0); 分别创建了两个哑节点（dummy nodes），用于构建小于x的节点链表和大于等于x的节点链表。
2. ListNode curSmall = small; 和 ListNode curBig = big; 分别初始化了两个指针，用于在构建链表时移动。
3. while (head != null) 循环遍历原链表的每个节点。
4. 在循环内部，通过判断 head.val < x 来决定当前节点应该放入哪个链表：

• 如果 head.val < x，则将当前节点加入到small链表的末尾，并移动small指针。
• 否则，将当前节点加入到big链表的末尾，并移动big指针。

5. head = head.next; 移动原链表的指针到下一个节点。
6. big.next = null; 确保大于等于x的链表的最后一个节点的next指针指向null，防止形成环。
7. small.next = curBig.next; 将小于x的链表的末尾连接到大于等于x的链表的第一个实际节点。
8. return curSmall.next; 返回新链表的头节点，由于curSmall是一个哑节点，所以返回curSmall.next。

146. LRU 缓存

请你设计并实现一个满足  LRU (最近最少使用) 缓存 约束的数据结构。

实现 LRUCache 类：

• LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
• int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
• void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。

函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

示例：

输入
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出
[null, null, null, 1, null, -1, null, -1, 3, 4]

解释
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1);    // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
lRUCache.get(2);    // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
lRUCache.get(1);    // 返回 -1 (未找到)
lRUCache.get(3);    // 返回 3
lRUCache.get(4);    // 返回 4

提示：

• 1 <= capacity <= 3000
• 0 <= key <= 10000
• 0 <= value <= 105
• 最多调用 2 * 105 次 get 和 put

class LRUCache extends LinkedHashMap<Integer, Integer>{
    private int capacity;
    
    public LRUCache(int capacity) {
        super(capacity, 0.75F, true);
        this.capacity = capacity;
    }

    public int get(int key) {
        return super.getOrDefault(key, -1);
    }

    public void put(int key, int value) {
        super.put(key, value);
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
        return size() > capacity; 
    }
}

1. private int capacity; 声明了一个私有变量capacity，用于存储缓存的最大容量。
2. 构造函数public LRUCache(int capacity)：

• super(capacity, 0.75F, true); 调用父类LinkedHashMap的构造函数，初始化一个具有指定容量、加载因子为0.75、按照访问顺序排序的LinkedHashMap。这里的true表示按照访问顺序排序，这是实现LRU缓存的关键。
• this.capacity = capacity; 将传入的容量赋值给成员变量capacity。

3. public int get(int key) 方法：

• return super.getOrDefault(key, -1); 调用LinkedHashMap的getOrDefault方法来获取键对应的值。如果键不存在，则返回-1。

4. public void put(int key, int value) 方法：

• super.put(key, value); 调用LinkedHashMap的put方法来插入或更新键值对。由于LinkedHashMap已经按照访问顺序排序，这个操作同时会更新键值对的访问顺序。

5. protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) 方法：

• return size() > capacity; 当LinkedHashMap的大小超过缓存容量时，返回true，指示LinkedHashMap移除最老的条目（即最少访问的条目）。这是实现LRU缓存淘汰策略的关键部分。