49、面试高频题（二）：链表反转、合并两个有序链表、判断链表是否有环、LRU缓存实现
说实话，链表这块是面试里的“钉子户”。
我面过不少人，前面聊得挺好，一到手写链表题就卡壳。其实不是不会，是紧张加上平时练得少。今天我把这四道高频题掰开揉碎讲清楚，你跟着走一遍，心里就有底了。
一、链表反转
这道题我当年第一次面大厂时就遇到了。面试官说“写个反转链表”，我脑子嗡一下——明明背过，手就是抖。
后来我总结了一个口诀：“三指针，步步移”。
核心思路：用三个指针 prev、curr、next 依次反转每个节点的指向。
// 反转单链表
struct ListNode* reverseList(struct ListNode* head) {
struct ListNode* prev = NULL;
struct ListNode* curr = head;
struct ListNode* next = NULL;
while (curr != NULL) {
next = curr->next; // 保存下一个节点
curr->next = prev; // 反转指向
prev = curr; // 前移
curr = next; // 前移
}
return prev; // 新头节点
}
我的小技巧：画图！拿张纸画三个节点，箭头标来标去，比看十遍代码都管用。
注意：别忘了处理空链表和只有一个节点的情况。我见过有人一上来就解引用 NULL，直接崩了。
二、合并两个有序链表
这道题其实很生活化。你想想看，两个有序的数组怎么合并？链表也一样，只是操作的是指针。
我个人习惯用递归写，代码短，逻辑清晰。但面试时最好两种都会——递归和迭代。
// 递归版本
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) {
if (l1 == NULL) return l2;
if (l2 == NULL) return l1;
if (l1->val < l2->val) {
l1->next = mergeTwoLists(l1->next, l2);
return l1;
} else {
l2->next = mergeTwoLists(l1, l2->next);
return l2;
}
}
避坑指南：我曾经在迭代版本里忘了更新尾指针，结果链表成了死循环。调试了一下午才发现。所以每次更新节点后，记得把尾指针往后挪。
三、判断链表是否有环
这道题有个经典解法——快慢指针。说白了就是两个人跑步，一个快一个慢，如果有环，快的迟早会追上慢的。
// 快慢指针判断环
bool hasCycle(struct ListNode *head) {
struct ListNode *slow = head;
struct ListNode *fast = head;
while (fast != NULL && fast->next != NULL) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) {
return true;
}
}
return false;
}
为什么快慢指针能相遇？因为每次移动，快指针比慢指针多走一步。如果有环，它们之间的距离每次减少1，最终一定会相遇。
注意：快指针移动时要检查 fast->next 是否为 NULL，否则会访问非法内存。嗯，这里一定要小心。
四、LRU缓存实现
LRU（Least Recently Used）缓存，说白了就是“最近最少使用”淘汰策略。我曾在项目中用LRU缓存来加速数据库查询，效果很明显。
实现LRU缓存，核心是哈希表 + 双向链表。哈希表保证O(1)查找，双向链表保证O(1)插入和删除。
// LRU缓存结构定义
typedef struct {
int key;
int value;
struct Node *prev;
struct Node *next;
} Node;
typedef struct {
int capacity;
int size;
Node *head; // 虚拟头节点
Node *tail; // 虚拟尾节点
Node **hash; // 哈希表
} LRUCache;
操作逻辑很简单：
- get(key)：如果存在，把节点移到链表头部；否则返回-1。
- put(key, value)：如果存在，更新值并移到头部；如果不存在，插入头部。如果容量满了，删除尾部节点。
我的经验：用虚拟头尾节点可以避免很多边界判断。我曾经不用虚拟节点，结果每次都要检查 head 和 tail 是否为 NULL，代码又臭又长。
知识体系总览
下面这张图把这四道题的核心逻辑串起来了，你可以对照着看。
总结一下
这四道题其实都围绕一个核心——指针操作。你只要把指针的指向变化搞清楚了，剩下的就是熟练度的问题。
我建议你每天手写一遍这四道题，坚持一周。面试时就算紧张，肌肉记忆也能帮你写出来。
嗯，链表这块其实没那么可怕。多画图，多动手，你也能成为别人眼中的“链表高手”。