【面试高频题】链表高频面试题全解析II：7道必刷题目+详细解题思路

文章目录

• 链表基础速记
• 一、两数相加 🟡 中等
• • 题目描述
  • 解题思路
  • C++ 实现
• 二、两两交换链表中的节点 🟡 中等
• • 题目描述
  • 解题思路
  • C++ 实现
• 三、K 个一组翻转链表 🔴 困难
• • 题目描述
  • 解题思路
  • C++ 实现
• 四、随机链表的复制 🟡 中等
• • 题目描述
  • 解题思路
  • C++ 实现
• 五、排序链表 🟡 中等
• • 题目描述
  • 解题思路
  • C++ 实现
• 六、合并 K 个升序链表 🔴 困难
• • 题目描述
  • 解题思路
  • C++ 实现
• 七、LRU 缓存 🟡 中等
• • 题目描述
  • 解题思路
  • C++ 实现

LeetCode 上关于链表的题目非常多，覆盖了从基础到进阶的各类场景。以下按照知识点分类，整理了一些经典的笔试和面试高频题，附上题号及题目描述、解题思路、C++ 实现。

链表基础速记

链表题有几个万能技巧，掌握后大部分题目都能迎刃而解：

// 技巧一：哑节点（dummy node）—— 统一处理头节点边界
ListNode* dummy = new ListNode(0);
dummy->next = head;

// 技巧二：快慢双指针 —— 找中点 / 判环
ListNode* slow = head, *fast = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
}

// 技巧三：反转链表（迭代）
ListNode* prev = nullptr, *cur = head;
while (cur) {
ListNode* nxt = cur->next;
cur->next = prev;
prev = cur;
cur = nxt;
}
return prev;

💡 黄金法则：链表题 先画图再写代码，把指针指向画清楚，避免断链或死循环。

一、两数相加 🟡 中等

LeetCode 2. 两数相加

题目描述

给你两个非空的链表，表示两个非负的整数。它们每位数字都是按照逆序方式存储的，并且每个节点只能存储一位数字。请你将两个数相加，并以相同形式返回一个表示和的链表。

• 两个数都不含前导零（除了数字 0 本身）

输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.

解题思路

就像我们小学学的竖式加法，从个位开始逐位相加，满十进一：

• 同时遍历两个链表，对应位相加，别忘了加上进位 carry
• 每次计算 sum = val1 + val2 + carry，当前位的值为 sum % 10，进位为 sum / 10
• 任意一个链表还有节点，或者还有进位，就继续循环
• 用哑节点简化头节点处理

示例演示：l1 = [2,4,3]（代表 342），l2 = [5,6,4]（代表 465）

第1位：2+5+0=7, 进位=0 → 节点值 7
第2位：4+6+0=10, 进位=1 → 节点值 0
第3位：3+4+1=8, 进位=0 → 节点值 8

结果：[7,0,8]（代表 807）✓

🔑 关键：循环条件写成 l1 || l2 || carry，三者任意为真就继续，这样能优雅处理两链表长度不等以及最高位有进位的情况。

C++ 实现

class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode* dummy = new ListNode(0); // 哑节点
ListNode* cur = dummy;
int carry = 0; // 进位

while (l1 || l2 || carry) {
int sum = carry;
if (l1) { sum += l1->val; l1 = l1->next; }
if (l2) { sum += l2->val; l2 = l2->next; }

carry = sum / 10;
cur->next = new ListNode(sum % 10);
cur = cur->next;
}
ListNode* result = dummy->next;
delete dummy;
return result;
}
};

复杂度分析

• 时间复杂度：O(max(m, n))，m、n 分别为两链表长度
• 空间复杂度：O(max(m, n))，结果链表的长度

二、两两交换链表中的节点 🟡 中等

LeetCode 24. 两两交换链表中的节点

题目描述

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即只能进行节点交换）。

解题思路

每次取出相邻的两个节点进行交换，关键是维护好前后指针不断链。

用哑节点 dummy 作为起点，每轮操作涉及 4 个指针：

交换前：dummy → node1 → node2 → 后续…
交换后：dummy → node2 → node1 → 后续…

步骤分解：

• node1 = prev->next，node2 = node1->next
• 先让 node1->next = node2->next（node1 指向 node2 之后）
• 再让 node2->next = node1（node2 指向 node1，完成交换）
• 最后 prev->next = node2（前驱指向新的头 node2）
• prev 移动到 node1（此时 node1 在后面），继续下一轮

示例演示：1 → 2 → 3 → 4

第1轮：dummy → [1,2] 交换 → dummy → 2 → 1 → 3 → 4
第2轮： 在1后面 [3,4] 交换 → dummy → 2 → 1 → 4 → 3

结果：[2,1,4,3] ✓

🔑 关键：交换时操作顺序不能搞反，先断开 node1 和 node2 的连接，再重新连接，否则会丢失后续节点的引用。画图理清顺序是关键。

C++ 实现

class Solution {
public:
ListNode* swapPairs(ListNode* head) {
ListNode* dummy = new ListNode(0);
dummy->next = head;
ListNode* prev = dummy;

while (prev->next && prev->next->next) {
ListNode* node1 = prev->next;
ListNode* node2 = node1->next;

node1->next = node2->next; // step1：node1 跳过 node2
node2->next = node1; // step2：node2 指向 node1
prev->next = node2; // step3：前驱指向 node2

prev = node1; // prev 移到 node1（下一对的前驱）
}
ListNode* result = dummy->next;
delete dummy;
return result;
}
};

复杂度分析

• 时间复杂度：O(n)
• 空间复杂度：O(1)

三、K 个一组翻转链表 🔴 困难

LeetCode 25. K 个一组翻转链表

题目描述

给你链表的头节点 head，每 k 个节点为一组进行翻转，返回修改后的链表。如果节点总数不是 k 的整数倍，则最后剩余的节点保持原有顺序。

• 你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换

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

解题思路

这是"两两交换"的升级版，把每次交换 2 个，变成每次翻转 k 个。

整体思路分三步：

示例演示：1 → 2 → 3 → 4 → 5，k=2

找到 [1,2]，翻转 → [2,1]，继续处理 [3,4,5]
找到 [3,4]，翻转 → [4,3]，继续处理 [5]
[5] 不足 k=2，保持原样

结果：2 → 1 → 4 → 3 → 5 ✓

🔑 关键：每轮翻转前先用"数够 k 个"检查剩余长度，翻转后记录好 tail（原来的 head），因为翻转后它变成了这段的尾节点，需要和下一段拼接。

C++ 实现

class Solution {
// 翻转 [head, tail] 这段链表，返回新头节点
ListNode* reverse(ListNode* head, ListNode* tail) {
ListNode* prev = tail->next; // tail 的下一个作为终止标志
ListNode* cur = head;
while (prev != tail) {
ListNode* nxt = cur->next;
cur->next = prev;
prev = cur;
cur = nxt;
}
return tail; // 翻转后 tail 变成新头
}
public:
ListNode* reverseKGroup(ListNode* head, int k) {
ListNode* dummy = new ListNode(0);
dummy->next = head;
ListNode* pre = dummy;

while (head) {
ListNode* tail = pre;
// 检查剩余节点是否够 k 个
for (int i = 0; i < k; i++) {
tail = tail->next;
if (!tail) return dummy->next; // 不够 k 个，直接返回
}
ListNode* nxt = tail->next; // 保存下一段的起点

// 翻转 [head, tail] 这 k 个节点
reverse(head, tail);

// 拼接：pre → 新头(tail) → … → 新尾(head) → nxt
pre->next = tail;
head->next = nxt;

// 移动指针，准备下一轮
pre = head;
head = nxt;
}
ListNode* result = dummy->next;
delete dummy;
return result;
}
};

复杂度分析

• 时间复杂度：O(n)
• 空间复杂度：O(1)

四、随机链表的复制 🟡 中等

LeetCode 138. 随机链表的复制

题目描述

给你一个长度为 n 的链表，每个节点包含一个额外增加的 random 指针，该指针可以指向链表中的任何节点或空节点。

构造这个链表的深拷贝，深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。

输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]

struct Node {
int val;
Node* next;
Node* random;
};

解题思路

难点在于 random 指针可以指向任意位置，复制时新节点还没全部创建完，不知道 random 应该指向哪里。

方法：哈希表映射，分两步走：

• 第一步：遍历原链表，为每个节点创建对应的新节点，存入哈希表 map[原节点] = 新节点
• 第二步：再次遍历，利用哈希表设置新节点的 next 和 random 指针

示例演示：原链表 1(random→3) → 2(random→1) → 3(random→null)

第一步（建映射）：
map[1号] = 新1，map[2号] = 新2，map[3号] = 新3

第二步（连指针）：
新1.next = map[原1.next] = 新2
新1.random = map[原1.random] = 新3
新2.next = map[原2.next] = 新3
新2.random = map[原2.random] = 新1
…

完成深拷贝 ✓

🔑 关键：哈希表解决了"新节点还没创建就要引用它"的鸡生蛋问题。先全部创建，再统一连线，两步走逻辑清晰。

C++ 实现

class Solution {
public:
Node* copyRandomList(Node* head) {
if (!head) return nullptr;

unordered_map<Node*, Node*> mp; // 原节点 → 新节点

// 第一步：创建所有新节点
Node* cur = head;
while (cur) {
mp[cur] = new Node(cur->val);
cur = cur->next;
}

// 第二步：连接 next 和 random
cur = head;
while (cur) {
if (cur->next) mp[cur]->next = mp[cur->next];
if (cur->random) mp[cur]->random = mp[cur->random];
cur = cur->next;
}

return mp[head];
}
};

复杂度分析

• 时间复杂度：O(n)
• 空间复杂度：O(n)，哈希表存储映射关系

五、排序链表 🟡 中等

LeetCode 148. 排序链表

题目描述

给你链表的头节点 head，请你将其按升序排列并返回排序后的链表。

要求时间复杂度 O(n log n)，空间复杂度 O(1)。

解题思路

O(n log n) 的排序首选归并排序，链表天然适合归并（不需要额外数组，合并操作非常高效）。

三步走：

示例演示：4 → 2 → 1 → 3

分割：[4,2] 和 [1,3]
递归：[2,4] 和 [1,3]
合并：比较 2和1 → 1，比较 2和3 → 2，比较 4和3 → 3，剩 4

结果：1 → 2 → 3 → 4 ✓

🔑 找中点技巧：快慢指针，fast 走两步 slow 走一步。注意要在 slow 的前一个位置断开（slow 是右段头节点），避免无限递归。

C++ 实现

class Solution {
// 合并两个有序链表
ListNode* merge(ListNode* l1, ListNode* l2) {
ListNode* dummy = new ListNode(0);
ListNode* cur = dummy;
while (l1 && l2) {
if (l1->val <= l2->val) { cur->next = l1; l1 = l1->next; }
else { cur->next = l2; l2 = l2->next; }
cur = cur->next;
}
cur->next = l1 ? l1 : l2;
return dummy->next;
}
public:
ListNode* sortList(ListNode* head) {
if (!head || !head->next) return head; // 0或1个节点，直接返回

// 快慢指针找中点，slow 停在左段末尾
ListNode* slow = head, *fast = head->next;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
}

ListNode* mid = slow->next; // 右段头节点
slow->next = nullptr; // 从中点断开

ListNode* left = sortList(head); // 递归排序左段
ListNode* right = sortList(mid); // 递归排序右段
return merge(left, right); // 合并
}
};

复杂度分析

• 时间复杂度：O(n log n)
• 空间复杂度：O(log n)，递归栈深度

六、合并 K 个升序链表 🔴 困难

LeetCode 23. 合并 K 个升序链表

题目描述

给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。

解题思路

最直观的想法是两两合并，但效率不高。更好的方法是最小堆（优先队列）：

• 把所有链表的头节点放入最小堆
• 每次从堆中取出值最小的节点，接到结果链表
• 将该节点的 next 节点（如果有）重新加入堆
• 重复直到堆为空

这样每次都能 O(log k) 地找到当前最小值，总共 n 个节点，总时间 O(n log k)。

示例演示：lists = [[1,4,5],[1,3,4],[2,6]]

初始堆：{1(链表0), 1(链表1), 2(链表2)}
取出1(链表0)→加入4：堆{1,2,4}，结果：1
取出1(链表1)→加入3：堆{2,3,4}，结果：1→1
取出2(链表2)→加入6：堆{3,4,6}，结果：1→1→2
取出3→加入4：…
最终：1→1→2→3→4→4→5→6 ✓

🔑 关键：优先队列默认是最大堆，合并链表需要最小堆，要自定义比较器 greater<> 或 lambda。

C++ 实现

class Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
// 最小堆：按节点值从小到大排序
auto cmp = [](ListNode* a, ListNode* b) {
return a->val > b->val; // 小顶堆
};
priority_queue<ListNode*, vector<ListNode*>, decltype(cmp)> pq(cmp);

// 将所有链表头节点入堆
for (auto node : lists) {
if (node) pq.push(node);
}

ListNode* dummy = new ListNode(0);
ListNode* cur = dummy;

while (!pq.empty()) {
ListNode* node = pq.top(); pq.pop(); // 取最小节点
cur->next = node;
cur = cur->next;
if (node->next) pq.push(node->next); // 下一个入堆
}
ListNode* result = dummy->next;
delete dummy;
return result;
}
};

复杂度分析

• 时间复杂度：O(n log k)，n 为节点总数，k 为链表数量
• 空间复杂度：O(k)，堆的大小

七、LRU 缓存 🟡 中等

LeetCode 146. LRU 缓存

题目描述

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

• 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) 时间复杂度。

解题思路

LRU 的核心是：最近使用的放前面，最久未用的放后面，满了就删掉最后面那个。

需要两种数据结构配合：

• 双向链表：维护使用顺序，头部是最新使用的，尾部是最久未用的，插入/删除 O(1)
• 哈希表：key → 链表节点，实现 O(1) 查找

每次 get 或 put 操作：

• 命中：把对应节点移到链表头部（标记为最近使用）
• 未命中 put：在头部插入新节点；若超容量，删除尾部节点，同时从哈希表删除

示例演示：capacity=2

put(1,1)：链表[1]，map{1:node1}
put(2,2)：链表[2,1]，map{1,2}
get(1)： 链表[1,2]（1移到头），返回 1
put(3,3)：超容量，删尾部的 2，插入 3 → 链表[3,1]，map{1,3}
get(2)： 不存在，返回 -1 ✓

🔑 关键：使用带头尾哑节点的双向链表，避免处理空链表的边界情况，moveToFront 和 removeTail 操作都非常简洁。

C++ 实现

class LRUCache {
struct Node {
int key, val;
Node *prev, *next;
Node(int k = 0, int v = 0) : key(k), val(v), prev(nullptr), next(nullptr) {}
};

int cap;
unordered_map<int, Node*> mp; // key → 节点
Node* head; // 哑头节点（最近使用端）
Node* tail; // 哑尾节点（最久未用端）

// 把节点从当前位置摘除
void remove(Node* node) {
node->prev->next = node->next;
node->next->prev = node->prev;
}

// 把节点插到头部（head 之后）
void insertFront(Node* node) {
node->next = head->next;
node->prev = head;
head->next->prev = node;
head->next = node;
}

public:
LRUCache(int capacity) : cap(capacity) {
head = new Node();
tail = new Node();
head->next = tail;
tail->prev = head;
}

int get(int key) {
if (!mp.count(key)) return –1;
Node* node = mp[key];
remove(node); // 从当前位置摘除
insertFront(node); // 移到头部（最近使用）
return node->val;
}

void put(int key, int value) {
if (mp.count(key)) {
// key 已存在：更新值，移到头部
Node* node = mp[key];
node->val = value;
remove(node);
insertFront(node);
} else {
// key 不存在：新建节点插到头部
Node* node = new Node(key, value);
mp[key] = node;
insertFront(node);
if ((int)mp.size() > cap) {
// 超容量：删除尾部节点（最久未用）
Node* lru = tail->prev;
remove(lru);
mp.erase(lru->key);
delete lru;
}
}
}
};

复杂度分析

• 时间复杂度：get O(1)，put O(1)
• 空间复杂度：O(capacity)

📌 学习建议：链表题一定要养成画图的习惯，每一步指针的指向都要在纸上画出来。遇到指针操作顺序不确定时，优先画图再写代码，能避免 90% 的 bug。建议按 #2 → #24 → #25 → #138 → #148 → #23 → #146 的顺序刷，难度循序渐进。