链表算法专题：反转、合并、LRU 与 C++ 实战

一、链表概述：单/双/循环链表

链表（Linked List）是一种线性数据结构，由一系列节点（Node）组成，每个节点包含数据域和指针域。与数组的连续内存不同，链表通过指针将零散的内存块串联起来，实现了灵活的动态内存管理。

1.1 三种链表结构图解

根据指针方向和首尾连接方式，链表分为单链表、双链表和循环链表三种基础形态。

1.2 链表节点的 C++ 定义

三种链表的核心差异体现在节点结构上：

// 单链表节点：LeetCode 标准定义
struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

// 双链表节点：LRU 等场景使用
struct DListNode {
    int key;
    int val;
    DListNode* prev;
    DListNode* next;
    DListNode(int k, int v) : key(k), val(v), prev(nullptr), next(nullptr) {}
};

二、链表反转原理

链表反转是最经典的链表操作，面试出现率极高。核心思想是把每个节点的 next 指针从"指向下一个"改为"指向前一个"。实现方式主要有两种：三指针迭代法和递归回溯法。

2.1 三指针迭代法原理

迭代法使用三个指针 prev、curr、next，边走边改指针方向，是面试中最推荐的写法。

2.2 递归回溯法原理

递归法思路更巧妙：一路递归到尾节点，回溯时逐层反转 next 指针。尾节点本身就是新头，逐层向上传。

三、反转示例：LeetCode 206 迭代+递归

题目（LeetCode 206 反转链表）：给定单链表的头节点 head，请你反转链表，并返回反转后的链表。

3.1 示例输入输出

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

3.2 解法一：三指针迭代（推荐）

#include <iostream>
using namespace std;

// LeetCode 标准单链表节点定义
struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

// 解法一：三指针迭代法 O(n) / O(1)
ListNode* reverseList(ListNode* head) {
    ListNode* prev = nullptr;  // 前驱指针，初始为 NULL（新链表的尾部）
    ListNode* curr = head;     // 当前指针，从原头节点开始遍历
    ListNode* next = nullptr;  // 暂存下一个节点，防止断链

    while (curr != nullptr) {
        next = curr->next;      // ① 先保存下一个节点
        curr->next = prev;      // ② 反转当前节点的 next 指针
        prev = curr;            // ③ prev 前移一步
        curr = next;            // ④ curr 前移一步
    }
    return prev;  // 循环结束时 curr=NULL，prev 就是新的头节点
}

// 辅助函数：从数组构造链表
ListNode* buildList(int arr[], int n) {
    if (n == 0) return nullptr;
    ListNode* head = new ListNode(arr[0]);
    ListNode* p = head;
    for (int i = 1; i < n; ++i) {
        p->next = new ListNode(arr[i]);
        p = p->next;
    }
    return head;
}

// 辅助函数：打印链表
void printList(ListNode* head) {
    while (head) {
        cout << head->val;
        if (head->next) cout << " -> ";
        head = head->next;
    }
    cout << " -> NULL" << endl;
}

int main() {
    int arr[] = {1, 2, 3, 4, 5};
    ListNode* head = buildList(arr, 5);
    cout << "反转前: "; printList(head);
    head = reverseList(head);
    cout << "反转后: "; printList(head);
    return 0;
}

3.3 解法二：递归回溯

// 解法二：递归法 O(n) / O(n)（栈深度）
ListNode* reverseListRecursive(ListNode* head) {
    // 递归终止：空节点或最后一个节点，返回自己（它就是新头）
    if (head == nullptr || head->next == nullptr) {
        return head;
    }
    // ① 先递归处理后面的子链表，得到新头 newHead
    ListNode* newHead = reverseListRecursive(head->next);

    // ② 回溯：把子链表中 head 的后继反过来指向 head
    head->next->next = head;

    // ③ head 自己的 next 断开，防止出现环
    head->next = nullptr;

    return newHead;  // 新头层层向上传递，从不改变
}

四、合并两个有序链表原理

合并两个有序链表是双指针技巧的经典应用。核心思路：用两个指针分别遍历两条链，每次选值更小的节点接在结果链上，直到某条链遍历完，把另一条链剩余部分整条接上。

4.1 双指针逐步骤合并图解

五、合并示例：LeetCode 21

题目（LeetCode 21 合并两个有序链表）：将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

5.1 示例输入输出

输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]

5.2 完整 C++ 代码

#include <iostream>
using namespace std;

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

// 合并两个有序链表：哨兵头 + 双指针 O(m+n) / O(1)
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    // 哨兵节点（dummy head）：值无意义，只用来简化头节点处理
    ListNode* dummy = new ListNode(0);
    ListNode* prev = dummy;  // 结果链的"当前尾部"

    ListNode* p1 = l1;       // 遍历 L1 的指针
    ListNode* p2 = l2;       // 遍历 L2 的指针

    // 当两条链都还有节点时，谁小接谁
    while (p1 != nullptr && p2 != nullptr) {
        if (p1->val <= p2->val) {
            prev->next = p1;   // 把 p1 接入结果链尾部
            p1 = p1->next;     // p1 前移
        } else {
            prev->next = p2;   // 把 p2 接入结果链尾部
            p2 = p2->next;     // p2 前移
        }
        prev = prev->next;     // 结果链尾部也要前移
    }

    // 此时至少有一条链已空，把另一条链剩余部分整条接上
    prev->next = (p1 != nullptr) ? p1 : p2;

    return dummy->next;  // 真正的头是 dummy 的下一个
}

// 辅助函数：构造链表
ListNode* build(int a[], int n) {
    if (!n) return nullptr;
    ListNode* h = new ListNode(a[0]);
    ListNode* p = h;
    for (int i = 1; i < n; ++i) {
        p->next = new ListNode(a[i]);
        p = p->next;
    }
    return h;
}

void print(ListNode* h) {
    while (h) { cout << h->val << " "; h = h->next; }
    cout << endl;
}

int main() {
    int a[] = {1, 2, 4};
    int b[] = {1, 3, 4};
    ListNode* l1 = build(a, 3);
    ListNode* l2 = build(b, 3);
    ListNode* res = mergeTwoLists(l1, l2);
    cout << "合并结果: ";
    print(res);
    return 0;
}

六、LRU 缓存原理

LRU（Least Recently Used，最近最少使用）是最经典的缓存淘汰策略。当缓存满了之后，再放入新数据时，优先删除"最久没有被访问过"的那条记录。

6.1 为什么用"哈希表 + 双链表"

单一数据结构满足不了需求：哈希表查值快 O(1)，但无法表达"最近使用"顺序；链表能表达顺序，但查找慢。所以把两者结合：

• 哈希表：key → 节点指针，实现 O(1) 定位节点
• 双链表：按"最近使用时间"排序，头部 = 最近使用，尾部 = 最久未使用

6.2 get/put 操作过程图解

七、LRU 示例：LeetCode 146

题目（LeetCode 146 LRU 缓存）：请你设计并实现一个满足 LRU 缓存约束的数据结构。实现 LRUCache 类：

• LRUCache(int capacity) 初始化容量
• int get(int key) 若 key 存在返回值，否则 -1
• void put(int key, int value) 存键值对，容量满时淘汰最久未用

7.1 完整 C++ 代码

#include <iostream>
#include <unordered_map>
using namespace std;

// 双链表节点：同时存 key 和 value
// key 必须保存，因为删除尾节点时需要从哈希表里同步删除，只能通过节点里的 key 反查
struct DListNode {
    int key;         // 存 key：删节点时用来 erase 哈希表
    int val;         // 存值
    DListNode* prev;
    DListNode* next;
    DListNode(int k = 0, int v = 0)
        : key(k), val(v), prev(nullptr), next(nullptr) {}
};

class LRUCache {
private:
    unordered_map<int, DListNode*> cache;  // key → 节点指针，O(1) 查
    DListNode* head;                        // 哨兵头，它的 next 是真正的"最近使用"
    DListNode* tail;                        // 哨兵尾，它的 prev 是真正的"最久未使用"
    int capacity;                           // 容量上限
    int size;                               // 当前节点数量

    // ---------- 4 个链表原子操作，全部 O(1) ----------

    // ① 把某个节点"加到头部"（head 之后第一个位置）
    //    用于：get 命中后、put 新插入时
    void addToHead(DListNode* node) {
        node->prev = head;
        node->next = head->next;
        head->next->prev = node;  // 先改原第一个节点的 prev
        head->next = node;        // 再改 head 的 next
    }

    // ② 从链表中移除某个节点（不释放内存，只摘链）
    //    因为是双链表，已知节点指针即可删除，无需遍历
    void removeNode(DListNode* node) {
        node->prev->next = node->next;
        node->next->prev = node->prev;
    }

    // ③ 把某个节点"移到头部" = 先摘出来 + 再加到头
    //    用于：get 命中、put 更新已有 key
    void moveToHead(DListNode* node) {
        removeNode(node);
        addToHead(node);
    }

    // ④ 删除尾部的真实节点（tail.prev，最久未使用）并返回它
    //    返回是为了拿到它的 key，好同步 erase 哈希表
    DListNode* removeTail() {
        DListNode* res = tail->prev;
        removeNode(res);
        return res;
    }

public:
    // 构造函数：初始化容量、哨兵头和尾
    LRUCache(int cap) : capacity(cap), size(0) {
        head = new DListNode();
        tail = new DListNode();
        head->next = tail;  // 两个哨兵互相连上 → 形成空链表
        tail->prev = head;
    }

    // get：命中则取值并移头，否则 -1
    int get(int key) {
        if (!cache.count(key)) {
            return -1;  // 未命中
        }
        DListNode* node = cache[key];
        moveToHead(node);  // 命中后：标记为最近使用
        return node->val;
    }

    // put：区分"key 已存在"和"key 不存在"
    void put(int key, int value) {
        if (cache.count(key)) {
            // 情况一：key 已存在 → 改值 + 移头
            DListNode* node = cache[key];
            node->val = value;
            moveToHead(node);
        } else {
            // 情况二：key 不存在 → 新建节点
            DListNode* newNode = new DListNode(key, value);
            cache[key] = newNode;   // 写入哈希表
            addToHead(newNode);    // 接入头部
            size++;

            // 若超出容量 → 删除 LRU 节点（尾部真实节点）
            if (size > capacity) {
                DListNode* tailNode = removeTail();  // 从双链表删除
                cache.erase(tailNode->key);           // 同步从哈希表删除！
                delete tailNode;                       // 释放内存
                size--;
            }
        }
    }
};

int main() {
    LRUCache lru(2);          // 容量 2
    lru.put(1, 1);            // [(1,1)]
    lru.put(2, 2);            // [(2,2), (1,1)]   头=2 尾=1
    cout << lru.get(1) << endl;  // 命中 1，移头：[(1,1), (2,2)] → 输出 1
    lru.put(3, 3);            // 容量满，踢 2(LRU)，插入 3 头：[(3,3), (1,1)]
    cout << lru.get(2) << endl;  // 没命中 → -1
    lru.put(4, 4);            // 踢 1，插入 4：[(4,4), (3,3)]
    cout << lru.get(1) << endl;  // -1
    cout << lru.get(3) << endl;  // 3
    cout << lru.get(4) << endl;  // 4
    return 0;
}

八、总结

链表三大核心技法——反转、合并、LRU——是算法面试的常青树。它们本质上是指针操作的三种典型模式：原地改向（反转）、多链协同（合并）、数据结构组合（LRU）。

延伸学习建议

• 反转进阶：LeetCode 92「反转链表 II（区间反转）」和 LeetCode 25「K 个一组翻转链表」——它们是 206 的翻版，难点在于"把断开的前后段重新接好"
• 合并进阶：LeetCode 23「合并 K 个升序链表」——把双指针换成 priority_queue 维护 K 个指针即可
• 缓存进阶：LeetCode 460「LFU 缓存」——同一频率再套一条链表，是 LRU 的升级版本
• 综合套路：链表题必画小图（3~4 个节点），写代码时变量名保持 prev/curr/next 一致，可大幅减少断链 Bug