前言：📫 作者简介：小明java问道之路，专注于研究计算机底层，就职于金融公司后端高级工程师，擅长交易领域的高安全/可用/并发/性能的设计和架构📫
🏆 Java领域优质创作者、阿里云专家博主、华为云享专家🏆
🔥 如果此文还不错的话，还请👍关注、点赞、收藏三连支持👍一下博主哦
本文导读
字节跳动企业题库，链表系列，因为有leetcode会员能看到企业出题频率，那我们从出题频率最高刷到最低，题目有21. 合并两个有序链表 、146. LRU缓存机制
21. 合并两个有序链表
【简单】【题目描述】将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例 1：输入：l1 = [1,2,4], l2 = [1,3,4] 输出：[1,1,2,3,4,4]
示例 2：输入：l1 = [], l2 = [] 输出：[]
示例 3：输入：l1 = [], l2 = [0] 输出：[0]
这道题是一到老生常谈的题目，对于熟悉链表的同学来说是秒杀的，我们分递归和迭代两种方法解题
【迭代、递归】图解：
代码详解，逐行注释：
/** * 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 { /* 递归法：O(m+n)，空间复杂度O(m+n) */ public ListNode mergeTwoLists(ListNode l1, ListNode l2) { // 如果两个链表有一个为空，递归结束。 if (l1 == null) { return l2; } if (l2 == null) { return l1; } // 判断 l1 和 l2 哪一个链表的头节点的值更小，然后递归地决定下一个添加到结果里的节点。 if (l1.val < l2.val) { l1.next = mergeTwoLists(l1.next, l2); return l1; } else { l2.next = mergeTwoLists(l1, l2.next); return l2; } } }
146. LRU缓存机制
【中等】【题目描述】运用你所掌握的数据结构，设计和实现一个LRU(最近最少使用) 缓存机制
实现 LRUCache 类：
LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存
int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
void put(int key, int value) 如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字-值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。
进阶：你是否可以在 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
【模拟法】图解：
代码详解，逐行注释：
publicclassLRUCache { classDLinkedNode { intkey; intvalue; DLinkedNodeprev; DLinkedNodenext; publicDLinkedNode() {} publicDLinkedNode(int_key, int_value) {key=_key; value=_value;} } privateMap<Integer, DLinkedNode>cache=newHashMap<Integer, DLinkedNode>(); privateintsize; privateintcapacity; privateDLinkedNodehead, tail; publicLRUCache(intcapacity) { this.size=0; this.capacity=capacity; // 使用伪头部和伪尾部节点head=newDLinkedNode(); tail=newDLinkedNode(); head.next=tail; tail.prev=head; } publicintget(intkey) { DLinkedNodenode=cache.get(key); if (node==null) { return-1; } // 如果 key 存在，先通过哈希表定位，再移到头部moveToHead(node); returnnode.value; } publicvoidput(intkey, intvalue) { DLinkedNodenode=cache.get(key); if (node==null) { // 如果 key 不存在，创建一个新的节点DLinkedNodenewNode=newDLinkedNode(key, value); // 添加进哈希表cache.put(key, newNode); // 添加至双向链表的头部addToHead(newNode); ++size; if (size>capacity) { // 如果超出容量，删除双向链表的尾部节点DLinkedNodetail=removeTail(); // 删除哈希表中对应的项cache.remove(tail.key); --size; } } else { // 如果 key 存在，先通过哈希表定位，再修改 value，并移到头部node.value=value; moveToHead(node); } } privatevoidaddToHead(DLinkedNodenode) { node.prev=head; node.next=head.next; head.next.prev=node; head.next=node; } privatevoidremoveNode(DLinkedNodenode) { node.prev.next=node.next; node.next.prev=node.prev; } privatevoidmoveToHead(DLinkedNodenode) { removeNode(node); addToHead(node); } privateDLinkedNoderemoveTail() { DLinkedNoderes=tail.prev; removeNode(res); returnres; } } /*** Your LRUCache object will be instantiated and called as such:* LRUCache obj = new LRUCache(capacity);* int param_1 = obj.get(key);* obj.put(key,value);*/
