当前位置：首页 > news >正文

面试硬核双杀！合并 K 个升序链表 + LRU 缓存｜力扣高频手撕原题全解

news 2026/8/17 3:15:44

23. 合并 K 个升序链表

题目链接

题目简介

解题思路

满分代码（规范注释 + 极简优雅）

核心亮点

146. LRU 缓存

题目链接

题目简介

解题思路

满分代码（手撕标准模板）

核心亮点

23. 合并 K 个升序链表

题目链接

23. 合并 K 个升序链表 - 力扣（LeetCode）

题目简介

给你一个链表数组，每个链表都已经按升序排列，请你将所有链表合并到一个升序链表中，返回合并后的链表。

解题思路

暴力合并 k 个链表时间复杂度极高，最优解：分治思想 + 归并排序核心逻辑极简清晰：

分：利用分治将 k 个链表不断拆分，直到拆分为两两一组的最小单元；
治：复用「合并两个有序链表」的模板，将拆分后的链表两两合并；
合：层层合并最终得到完整的升序链表。整体时间复杂度优化至O(n log k)，是面试标准解法！

满分代码（规范注释 + 极简优雅）

java

运行

/** * 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 { public ListNode mergeKLists(ListNode[] lists) { // 边界判断：空数组直接返回null if(lists == null || lists.length == 0){ return null; } // 分治递归合并 return slove(lists, 0, lists.length - 1); } // 分治核心：拆分链表，两两合并 public ListNode slove(ListNode[] arr, int left, int right){ // 递归终止：只剩一个链表，无需合并 if(left == right) { return arr[left]; } // 找中点，拆分左右两部分 int mid = (left + right) / 2; ListNode lnode = slove(arr, left, mid); ListNode rnode = slove(arr, mid + 1, right); // 合并两个有序链表 return merger(lnode, rnode); } // 模板：合并两个升序链表 public ListNode merger(ListNode left, ListNode right){ // 虚拟头节点，简化拼接操作 ListNode res = new ListNode(Integer.MIN_VALUE); ListNode h = res; // 双指针遍历，按大小拼接 while(left != null && right != null){ if(left.val < right.val){ h.next = left; left = left.next; }else{ h.next = right; right = right.next; } h = h.next; } // 拼接剩余节点 h.next = left != null ? left : right; return res.next; } }

核心亮点

分治思想完美解决 k 链表合并问题，复杂度最优；
复用双指针合并有序链表模板，代码简洁无冗余；
面试高频默写题，思路固定易掌握。

146. LRU 缓存

题目链接

146. LRU 缓存 - 力扣（LeetCode）

题目简介

请你设计并实现一个满足LRU (最近最少使用) 缓存约束的数据结构，实现get获取数据和put写入数据方法，超出容量时自动删除最久未使用的数据。

解题思路

LRU 是面试手撕天花板，核心设计：双向链表 + 哈希表

双向链表：维护节点使用顺序，头部存最新使用节点，尾部存最久未使用节点，方便快速增删；
哈希表：O (1) 时间定位节点，解决链表查找慢的问题；
核心操作：

- get：查询节点，存在则刷新到链表头部；
- put：新增 / 更新节点，超容则删除尾部节点。

满分代码（手撕标准模板）

java

运行

class LRUCache { // 自定义双向链表节点 class Node { int key; int value; Node pre; Node next; } // 缓存容量 private int capacity; // 双向链表头尾节点 private Node first; private Node last; // 哈希表：O(1)定位节点 private Map<Integer, Node> map; // 初始化LRU缓存 public LRUCache(int capacity) { this.capacity = capacity; map = new HashMap<>(); } // 获取节点值 public int get(int key) { Node node = map.get(key); // 节点不存在返回-1 if(node == null){ return -1; } // 刷新节点到链表头部（标记为最近使用） moveToHead(node); return node.value; } // 写入/更新节点 public void put(int key, int value) { Node node = map.get(key); if(node == null){ // 新增节点 node = new Node(); node.key = key; node.value = value; // 容量超限，删除最久未使用（尾部节点） if(map.size() == capacity){ removeLast(); } // 添加到头部并更新哈希表 addToHead(node); map.put(key, node); }else{ // 更新节点值，并刷新到头部 node.value = value; moveToHead(node); } } // 将节点移动到链表头部 public void moveToHead(Node node){ // already 头部，直接返回 if(node == first){ return; } // 是尾部节点，更新尾指针 if(node == last){ last.pre.next = null; last = last.pre; }else{ // 中间节点，断开前后连接 node.pre.next = node.next; node.next.pre = node.pre; } // 插入头部 node.next = first; first.pre = node; first = node; } // 删除尾部节点（最久未使用） public void removeLast(){ map.remove(last.key); Node lastPre = last.pre; if(lastPre != null){ lastPre.next = null; last = lastPre; } } // 添加节点到头部 public void addToHead(Node node){ // 空缓存，头尾都是当前节点 if(map.isEmpty()){ first = node; last = node; }else{ node.next = first; first.pre = node; first = node; } } } /** * 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); */