LeetCode 链表高频双题精讲：146. LRU 缓存 + 148. 排序链表，吃透双向链表与归并排序

🔥你好我是fengxin_rou这是我的个人主页fengxin_rou的主页

❄️欢迎查看我的专栏我的专栏

《Java后端学习》、《JAVASE基础》、《JUC并发》、《redis》、《JVM虚拟机》、《MYSQL》、《黑马点评》、《rabbitmq》、《JavaWeb+AI的talis学习系统》、《苍穹外卖》

目录

一、146. LRU 缓存

1. 题目本质

2. 为什么不能只用一种结构

3. 先把模型搭起来

4. 先写 3 个工具方法

5. 完整代码

6. get 和 put 到底在做什么

7. 这题最容易写错的地方

8. 复杂度分析

二、148. 排序链表

1. 为什么这题第一反应应该是归并排序

2. 整体思路只有 3 步

3. 完整代码

4. 递归过程怎么理解

5. middleNode 为什么要带一个 pre

6. mergeTwoList 是这题的稳定器

7. 复杂度分析

三、把这两题放在一起看，你会更容易记住

四、最后总结

前言：

很多人一看到链表，脑海里只有“快慢指针”。但真正的高频题更想考的是：你能不能把链表当成一个可维护的数据结构来设计，或者把链表塞进一个更高效的算法框架里。

这篇文章我用两道经典题，把链表里最容易卡住的两条主线串起来：

• 146. LRU 缓存：链表不是拿来遍历的，而是拿来维护“访问顺序”的。
• 148. 排序链表：链表不适合随机访问，所以排序时要优先想到归并排序。

阅读收益：看完这篇，你不仅能写出这两题，还能知道为什么一个要用“哈希表 + 双向链表”，另一个要用“分治 + 归并”。

一、146. LRU 缓存

1. 题目本质

LRU 的全称是 Least Recently Used，意思是“最近最少使用”。题目要求我们在 O(1) 平均时间复杂度内完成两件事：

同时，当容量满了以后，还要能立刻淘汰掉“最久没有被访问”的那个元素。

2. 为什么不能只用一种结构

所以这题的标准答案一定是：HashMap 负责定位节点，双向链表负责维护访问顺序。

3. 先把模型搭起来

我们把“最近访问”的节点放在链表头部，把“最久没访问”的节点放在链表尾部。为了让边界处理更统一，再加一个哨兵节点 dummy，让链表首尾闭环。

一句话记忆：Map 找节点，双向链表挪节点，尾部淘汰旧节点。

4. 先写 3 个工具方法

• remove(x)：把节点 x 从当前链表位置删掉。
• pushFront(x)：把节点 x 插到链表最前面。
• getNode(key)：先从 Map 找节点，找到后顺手移动到最前面。

很多同学这题写乱，往往不是错在 get 和 put，而是这 3 个基础操作没有拆开。

5. 完整代码

class LRUCache {
private static class Node {
int key, value;
Node prev, next;

Node(int key, int value) {
this.key = key;
this.value = value;
}
}

private final int capacity;
private final Node dummy = new Node(0, 0);
private final Map<Integer, Node> keyToNode = new HashMap<>();

public LRUCache(int capacity) {
this.capacity = capacity;
dummy.next = dummy;
dummy.prev = dummy;
}

public int get(int key) {
Node node = getNode(key);
return node == null ? -1 : node.value;
}

public void put(int key, int value) {
Node node = getNode(key);
if (node != null) {
node.value = value;
return;
}

node = new Node(key, value);
keyToNode.put(key, node);
pushFront(node);

if (keyToNode.size() > capacity) {
Node oldest = dummy.prev;
keyToNode.remove(oldest.key);
remove(oldest);
}
}

private Node getNode(int key) {
if (!keyToNode.containsKey(key)) {
return null;
}
Node node = keyToNode.get(key);
remove(node);
pushFront(node);
return node;
}

private void remove(Node x) {
x.prev.next = x.next;
x.next.prev = x.prev;
}

private void pushFront(Node x) {
x.prev = dummy;
x.next = dummy.next;
x.prev.next = x;
x.next.prev = x;
}
}

6. get 和 put 到底在做什么

get：如果 key 不存在，直接返回 -1；如果存在，说明这个元素刚刚被访问过，就必须移到最前面。

put：如果 key 已存在，只更新值并把它挪到最前面；如果不存在，就新建节点塞到头部。如果超容量，就删除尾部节点。

7. 这题最容易写错的地方

• 只更新了值，没有把访问过的节点移到头部。
• 淘汰元素时先删链表、后删 Map，结果 key 对不上。
• 没有设置哨兵节点，导致空链表和单节点链表边界特别难处理。
• getNode 找到节点后忘了“先 remove 再 pushFront”。

8. 复杂度分析

无论是 get 还是 put，核心操作都是 HashMap 查找与双向链表插删，因此平均时间复杂度都是 O(1)，空间复杂度是 O(capacity)。

二、148. 排序链表

1. 为什么这题第一反应应该是归并排序

数组排序时，我们很自然会想到快排。但链表和数组最大的区别在于：链表不支持随机访问。这意味着快排里很多“按下标定位”的动作都不够友好。

反过来，归并排序特别适合链表，因为：

• 找中点可以用快慢指针。
• 合并两个有序链表本来就是链表的强项。
• 题目要求时间复杂度 O(n log n)，归并排序刚好匹配。

2. 整体思路只有 3 步

关键细节：我们不是只找中点 slow，而是还要保留中点前一个节点 pre，这样才能执行 pre.next = null 完成断链。

3. 完整代码

class Solution {
public ListNode sortList(ListNode head) {
if (head == null || head.next == null) {
return head;
}

ListNode head2 = middleNode(head);
head = sortList(head);
head2 = sortList(head2);
return mergeTwoList(head, head2);
}

private ListNode middleNode(ListNode head) {
ListNode pre = head;
ListNode slow = head;
ListNode fast = head;

while (fast != null && fast.next != null) {
pre = slow;
slow = slow.next;
fast = fast.next.next;
}

pre.next = null;
return slow;
}

private ListNode mergeTwoList(ListNode head1, ListNode head2) {
ListNode dummy = new ListNode();
ListNode cur = dummy;

while (head1 != null && head2 != null) {
if (head1.val < head2.val) {
cur.next = head1;
head1 = head1.next;
} else {
cur.next = head2;
head2 = head2.next;
}
cur = cur.next;
}

cur.next = head1 != null ? head1 : head2;
return dummy.next;
}
}

4. 递归过程怎么理解

我们可以把它想成“先拆后治”。一条很长的链表，先不断切成更短的小链表，直到每段长度只有 1，这时天然有序。然后从最底层开始，两两合并成更长的有序链表，最后一路合并回去。

5. middleNode 为什么要带一个 pre

如果你只返回 slow，你确实能找到中点，但你没法把原链表切断。递归排序最怕的就是没有真正断链，结果左半部分和右半部分还连着，直接进入死递归。

6. mergeTwoList 是这题的稳定器

只要“合并两个有序链表”写熟了，这题就基本稳了。它本质上和合并两个有序数组的思路一样，只不过数组是比大小后写入新数组，链表是比大小后把较小节点接到结果链表后面。

7. 复杂度分析

每一层递归都会遍历所有节点一次，而递归层数是 log n，因此时间复杂度是 O(n log n)。如果只看递归栈，额外空间复杂度是 O(log n)。

三、把这两题放在一起看，你会更容易记住

一个在考你“如何维护顺序”，一个在考你“如何利用链表特性做排序”。虽然题型不同，但底层共识其实一样：不要把链表当弱化版数组去写，而是要顺着它的结构特点去设计解法。

四、最后总结

如果题目要求 O(1) 插删 + 维护访问顺序：优先想到双向链表。

如果题目要求链表排序，尤其是 O(n log n)：优先想到归并排序。

如果你发现自己总在边界上出错：多用哨兵节点、拆工具方法、先断链再递归。

链表题并不可怕，怕的是“每次都现场想指针怎么改”。真正稳定的做法，是把高频动作沉淀成模板。像 LRU 里的 remove / pushFront，排序链表里的 找中点 / 断链 / 合并有序链表，其实都属于以后会反复复用的套路。

如果你愿意，我下一篇可以继续把链表高频题串成一个系列，比如 反转链表、K 个一组翻转、复制带随机指针的链表、合并 K 个升序链表，这样整个链表专题会更完整。

文章适合直接作为 CSDN 草稿基础版继续补图、补题目链接、补题后反思。