ZaynPei Lv6
  2025-11-05 16:16:52 2025-11-05 16:16:52 Created   2025-11-22 23:18:16 2025-11-22 23:18:16 Updated  5.4k Words  24 Mins

链表

链表是一种线性数据结构，由一系列节点组成，每个节点包含数据和指向下一个节点的指针。链表的主要类型包括单向链表、双向链表和循环链表。链表适合频繁的插入和删除操作，因为这些操作不需要移动其他元素。

两个黄金问题

对于链表, 有两个黄金问题, 贯穿了绝大多数链表题目的解法思路.

什么时候用哨兵节点 (Dummy Node)？

  • 答案：任何时候可能会修改（删除或插入）链表的头节点 (head)时，都应该使用哨兵节点。
  • 为什么？
    • 统一逻辑：常规操作中，删除一个节点 curr 需要操作它的前一个节点 prev（即 prev->next = curr->next）。
    • 痛点：但如果你要删除的是头节点 head 呢？head 没有 prev！
    • 常规解法：你需要写一个 if (curr == head) 的特殊判断，这非常繁琐且容易出错。
    • 哨兵解法：创建一个ListNode* dummy = new ListNode(0);，并让 dummy->next = head;
      • 现在，原 head 节点也有了一个“前驱”节点 dummy。
      • 你所有的操作都可以从 dummy 节点开始，如果要删除 prev->next 所指向的元素, 所有的删除逻辑都统一成了 prev->next = prev->next->next。
      • 最后返回：dummy->next（这可能是原来的 head，也可能是新的 head）。
  • 典型案例：
    • 删除节点 (如 203. 移除链表元素, 82. 删除排序链表中的重复元素 II)
    • 合并链表 (如 21. 合并两个有序链表) - dummy 用来作为新链表的“假头”。

while (node != nullptr) vs while (node->next != nullptr)？

  • 这是一个关于循环终止条件的精髓问题，决定了你的指针最后“停在”哪里。
  • while (node != nullptr)
    • 含义：我会处理 node，直到 node 变为 nullptr 为止。
    • 循环体：在循环内部，node 是 你要处理的当前节点。
    • 终止时：node 的值是 nullptr。你已经走过了（处理过了）最后一个节点。
    • 用途：
      • 遍历并访问所有节点的值（例如：打印链表、二进制求和）。
      • 反转链表（你需要处理最后一个节点）。
      • 示例：while (curr != nullptr) { … curr = curr->next; }
  • while (node->next != nullptr)
    • 含义：我会检查 node 的下一个节点，直到 node 的下一个是 nullptr 为止。
    • 循环体：在循环内部，node 是 你要处理的当前节点的前一个节点, 而 node->next 是 你要处理的当前节点。
    • 终止时：node 的值是 链表的最后一个节点 (node->next 是 nullptr)。
    • 用途：
      • 删除节点（你需要访问被删除节点的前一个节点）。
      • 寻找链表的尾节点（例如：在尾部添加新节点）。
      • 快慢指针中 fast 指针的检查（while (fast != nullptr && fast->next != nullptr)，因为你要访问 fast->next->next）。
      • 当你的操作涉及 node 和 node->next 两个节点时（例如：83. 删除排序链表中的重复元素）。

例如, 给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。(LC 203)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
ListNode* removeElements(ListNode* head, int val) {
    ListNode* dummy = new ListNode(0);
    dummy->next = head;   // 考虑到删除头节点的情况, 使用哨兵节点

    ListNode* prev = dummy;  // 因为删除节点需要访问前一个节点, 因此使用 while(prev->next!=nullptr)
    while(prev->next!=nullptr){  // 实际上是遍历 prev->next 节点
        if(val==prev->next->val){
            prev->next = prev->next->next;  // 注意如果删除后, prev 不变, 继续检查新的 prev->next. 否则会跳过新的 prev->next 节点
        }else{
            prev = prev->next;
        }
    }
    return dummy->next;
}

遍历链表

给你两个链表 list1 和 list2 , 请你将 list1 中下标从 a 到 b 的全部节点都删除，并将list2 接在被删除节点的位置。(LC 1669)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
ListNode* mergeInBetween(ListNode* list1, int a, int b, ListNode* list2) {
    
    // 步骤 1：找到 list2 的尾节点 (tail2)
    // 应用「while (node->next != nullptr)」原则
    // 目标：循环结束后，tail2 停在 list2 的最后一个节点上。
    ListNode* tail2 = list2;
    while (tail2->next != nullptr) {
        tail2 = tail2->next;
    }

    // 步骤 2：找到 list1 中第 a-1 个节点 (node_a_prev)
    // 
    // 我们需要一个指针从 head (索引 0) 开始，走 a-1 步。
    // for 循环是执行“固定步数”的最清晰的工具。
    ListNode* node_a_prev = list1;
    for (int i = 0; i < a - 1; ++i) {
        // i=0 时, cur 移动到索引 1
        // ...
        // i=a-2 时, cur 移动到索引 a-1
        node_a_prev = node_a_prev->next;
    }

    // 步骤 3：找到 list1 中第 b+1 个节点 (node_b_next)
    // 
    // 我们可以从 node_a_prev (索引 a-1) 继续出发。
    // 我们需要找到 b+1。
    // b+1 与 a-1 之间的步数差是：(b+1) - (a-1) = b - a + 2
    //
    // 我们让 node_b_next 从 node_a_prev 开始，
    // 再走 (b - a + 2) 步，它就会停在 b+1 节点上。
    ListNode* node_b_next = node_a_prev;
    for (int i = 0; i < (b - a + 2); ++i) {
        // i=0 时, cur 移动到索引 a
        // i=1 时, cur 移动到索引 a+1
        // ...
        // i=(b-a+1) 时, cur 移动到索引 b+1 (总共 b-a+2 步)
        node_b_next = node_b_next->next;
    }
    
    // 步骤 4：执行“链表手术”
    // 
    // 此时我们手上有三个关键节点：
    // 1. node_a_prev: list1 的第 a-1 个节点
    // 2. node_b_next: list1 的第 b+1 个节点
    // 3. tail2:       list2 的最后一个节点
    //
    // 我们只需要执行两次链接：
    
    // 1. 将 (a-1) 节点的 next 指向 list2 的头部
    node_a_prev->next = list2;
    
    // 2. 将 list2 的尾部 (tail2) 的 next 指向 (b+1) 节点
    tail2->next = node_b_next;

    // (可选：在非 LeetCode 环境下，这里应该释放 [a, b] 之间的节点)

    // 步骤 5：返回 list1
    // 因为头节点 (list1) 始终未变
    return list1;
}

链表排序

对链表排序, 常用的有两种: 归并排序 和 插入排序

插入排序: 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
Lclass Solution {
public:
    ListNode* sortList(ListNode* head) {
        // 步骤说明：处理空链表的边界情况。
        if (head == nullptr) {
            return nullptr;
        }

        // 步骤说明：创建一个“哨兵节点”(dummy)，它将是新排序链表的头节点。
        ListNode* dummy = new ListNode(0);
        ListNode* curr = head; // curr 是遍历原链表的指针

        // 步骤说明：遍历原链表中的每一个节点 (curr)。
        while (curr != nullptr) {
            // 步骤说明：为 curr 节点在“已排序”链表(dummy开头的)中找到插入位置。
            // prev 总是从已排序链表的头部(dummy)开始查找。
            ListNode* prev = dummy;
            
            // 步骤说明：查找插入位置。
            // 循环直到找到一个 prev->next 的值大于或等于 curr->val, 此时 prev 就是插入位置的前一个节点
            while (prev->next != nullptr && prev->next->val < curr->val) {
                prev = prev->next;
            }

            // 步骤说明：在移动 curr 之前，必须保存原链表的下一个节点。
            ListNode* nextNode = curr->next;

            // 步骤说明：执行插入。
            // 将 curr 插入到 prev 和 prev->next 之间。
            curr->next = prev->next;
            prev->next = curr;

            // 步骤说明：处理原链表的下一个节点。
            curr = nextNode;
        }

        // 步骤说明：返回已排序链表的真正头节点。
        return dummy->next;
    }
};

分治（Divide and Conquer）: 归并排序如下 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
class Solution {
public:
    ListNode* sortList(ListNode* head) {
        // 步骤说明：1. 递归终止条件（空链表或单节点链表）。
        if (head == nullptr || head->next == nullptr) {
            return head;
        }

        // 步骤说明：2. 寻找中点并断开链表。
        // 使用快慢指针, 每次 fast 走两步, slow 走一步
        // 当链表长度是偶数时，左右两半部分长度相等；当是奇数时，左半部分多一个节点
        // 'slow' 最终将指向左半部分的“尾节点”。
        ListNode* slow = head;
        ListNode* fast = head->next; // 关键：fast 从 head->next 开始

        while (fast != nullptr && fast->next != nullptr) {
            slow = slow->next;
            fast = fast->next->next;
        }

        // 步骤说明：此时 'slow' 在中点，'slow->next' 是右半部分的头。
        ListNode* rightHalf = slow->next;
        slow->next = nullptr; // 断开链表，这是关键一步。

        // 步骤说明：3. 递归排序左右两半。
        ListNode* left = sortList(head);      // 左半部分 [head...slow]
        ListNode* right = sortList(rightHalf); // 右半部分 [rightHalf...null]

        // 步骤说明：4. 合并两个已排序的链表。
        return mergeTwoLists(left, right);
    }

private:
    /**
     * 辅助函数：合并两个已排序的链表 (l1, l2)
     */
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode* dummy = new ListNode(0);
        ListNode* curr = dummy;

        while (l1 != nullptr && l2 != nullptr) {
            if (l1->val <= l2->val) {
                curr->next = l1;
                l1 = l1->next;
            } else {
                curr->next = l2;
                l2 = l2->next;
            }
            curr = curr->next;
        }

        // 步骤说明：连接剩余的链表部分。
        curr->next = (l1 != nullptr) ? l1 : l2;

        return dummy->next;
    }
};

反转链表

这是链表操作的“Hello World”，是所有复杂操作（如 K 个一组反转）的基础。你必须能徒手、快速、无误地写出它。

核心思想：你需要三个指针在遍历过程中协同工作。 - ListNode* prev：指向已反转部分的头，初始为 nullptr。 - ListNode* curr：指向正在处理的当前节点，初始为 head。 - ListNode* next_temp：临时保存 curr 的下一个节点，防止链表“断开”后丢失。

“穿针引线”四步法（循环体内）： - next_temp = curr->next; // 1. 暂存：保存好“下一个” - curr->next = prev; // 2. 反转：当前节点指向“前一个” - prev = curr; // 3. 步进：prev 移动到“当前” - curr = next_temp; // 4. 步进：curr 移动到“下一个”

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
ListNode* reverseList(ListNode* head) {
    // 步骤 1: 初始化三个指针
    ListNode* prev = nullptr;
    ListNode* curr = head;
    ListNode* next_temp = nullptr;

    // 步骤 2: 循环遍历
    // 使用 while (curr != nullptr) 因为我们要处理到最后一个节点
    while (curr != nullptr) {
        // 步骤 3: 穿针引线四步法
        next_temp = curr->next; // 1. 暂存
        curr->next = prev;      // 2. 反转
        prev = curr;            // 3. 步进 prev
        curr = next_temp;       // 4. 步进 curr
    }

    // 步骤 4: 返回
    // 循环结束时，curr 是 nullptr, prev 正好是原链表的尾，
    // 即新链表的头
    return prev;
}

LC 25: K 个一组反转链表. 给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。

一个比较容易理解的解法是: 先反转每一组节点, 然后再把这些反转后的节点组连接起来. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
ListNode* reverseList(ListNode* head, ListNode* tail) {
    ListNode* prev = tail->next;  // 反转后 tail 的下一个节点, 用于保持链表的连通性
    ListNode* curr = head;
    ListNode* next_temp = nullptr;
    ListNode* tail_next = tail->next; // 额外保存循环停止条件, 因为 tail 可能会变化

    while (curr != tail_next) {
        next_temp = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next_temp;
    }
    return prev;  // 返回反转后的头节点
}

ListNode* reverseKGroup(ListNode* head, int k) {
    if(k <= 1 || !head) return head;  // 如果 k <= 1 或链表为空, 不需要反转
    ListNode* dummy = new ListNode(0, head);  // 使用哨兵节点简化边界情况, 作为新链表的头节点

    vector<ListNode*> Head; // 存储每组的起始节点
    vector<ListNode*> Tail; // 存储每组的结束节点
    int cnt = 0;  // 计数节点
    ListNode* curr = head;

    while (curr != nullptr) {   // 循环中处理的是 curr 节点
        cnt++;
        
        if (cnt % k == 1) {         // 这里如果k==1会导致无法记录节点, 因此在函数开头处理k<=1的情况
                                    // 或者采取(cnt - 1) % k == 0 也可以处理
            Head.push_back(curr);  // 记录每组的起始节点
        }
        if (cnt % k == 0) {
            Tail.push_back(curr);  // 记录每组的结束节点
        }
        curr = curr->next;
    }

    int full_groups = cnt / k;  // 计算完整的 k 组数量
    ListNode* prevTail = dummy;  // 上一组的尾节点, 初始为哨兵节点
    for (int i = 0; i < full_groups; i++) {
        ListNode* currHead = Head[i];
        ListNode* currTail = Tail[i];
        ListNode* newHead = reverseList(currHead, currTail); // 反转当前组
        // 这里 reverseList 函数会返回反转后的头节点(即之前的尾节点), 同时会将反转后的尾节点指向下一组的头节点, 从而保持链表的连通性

        prevTail->next = newHead;  // 连接上一组和当前组, 这是核心步骤, 将上一组的尾节点指向当前组反转后的头节点
        prevTail = currHead;       // 更新 prevTail 为当前组的尾节点

    }
    ListNode* newHead = dummy->next;;
    delete dummy;  // 释放哨兵节点
    return newHead;
}
这个解法的时间复杂度是 O(N), 空间复杂度是 O(N/k) 用于存储每组的头尾节点. 如果想优化空间复杂度, 可以在遍历链表时, 每当遇到一组完整的 k 个节点时, 立即反转该组节点, 并连接到结果链表中, 这样就不需要额外存储每组的头尾节点了, 从而将空间复杂度优化到 O(1). 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
ListNode* reverseList(ListNode* head, ListNode* tail){
    ListNode* prev = tail->next;
    ListNode* curr = head;
    ListNode* next_temp = nullptr;
    ListNode* tail_next = tail->next; 

    while(curr != tail_next){
        next_temp = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next_temp;
    }
    return prev;
}

ListNode* reverseKGroup(ListNode* head, int k) {
    // 使用一个哨兵节点
    ListNode* dummy = new ListNode(0, head);
    
    // prevGroupTail 指向上一组的尾部, 初始时，它指向哨兵节点
    ListNode* prevGroupTail = dummy;
    
    // currGroupHead 指向当前组的头部
    ListNode* currGroupHead = head;

    while (currGroupHead != nullptr) {
        
        // 步骤 1：找到当前组的尾节点 (currGroupTail)
        ListNode* currGroupTail = currGroupHead;
        int count = 1;
        // 向前走 k-1 步
        while (count < k && currGroupTail != nullptr) {
            currGroupTail = currGroupTail->next;
            count++;
        }

        // 步骤 2：检查是否凑足了 k 个
        // 如果 currGroupTail 是 nullptr，说明剩余节点不足 k 个
        if (currGroupTail == nullptr) {
            break; // 循环终止，剩余部分保持原样
        }

        // 步骤 3：保存下一组的头节点，以便后续连接
        ListNode* nextGroupHead = currGroupTail->next;

        // 步骤 4：翻转当前组 [currGroupHead, currGroupTail]
        // 你的 reverseList 函数会返回翻转后的新头 (即 currGroupTail)
        // 并且自动将翻转后的新尾 (即 currGroupHead) 指向 nextGroupHead
        ListNode* newHead = reverseList(currGroupHead, currGroupTail);

        // 步骤 5：将上一组的尾部连接到当前组的新头部
        prevGroupTail->next = newHead; // 或者写 prevGroupTail->next = currGroupTail;

        // 步骤 6：推进指针，为下一次循环做准备
        // 翻转后，currGroupHead 变成了当前组的尾巴
        prevGroupTail = currGroupHead; 
        // 移动到下一组的头部
        currGroupHead = nextGroupHead;
    }

    // 释放哨兵节点并返回
    ListNode* newHead = dummy->next;
    delete dummy;
    return newHead;
}
### 快慢指针及前后指针

快慢指针是一种常用的链表技巧，使用两个指针以不同速度遍历链表，从而解决诸如寻找中间节点、检测环、寻找环的入口等问题。 - ListNode* slow：每次走 1 步。 - ListNode* fast：每次走 2 步 (fast = fast->next->next)。

循环条件：while (fast != nullptr && fast->next != nullptr) - （必须同时检查两者，使得fast和它的下一个节点都非空, 因为你要访问 fast->next->next）

找中点 (876. 链表的中间结点)： - 当 fast 走到终点（nullptr）时，slow 恰好在中点。 - （如果偶数个节点，slow 在后一个中点，符合题目要求）。

判环 (141. 环形链表)： - fast 走得快，slow 走得慢。 - 如果链表有环，fast 迟早会从“后面”追上 slow（fast == slow）。

倒数第 N 个 (19. 删除链表的倒数第 N 个结点)： - 这是“快慢”的变体，也叫前后指针。 - fast 先走 N 步。 - 然后 slow 和 fast 一起走（每次各走 1 步）。 - 当 fast 走到尾节点（fast->next == nullptr）时，slow 就停在倒数第 N+1 个节点上，即要删除节点的前驱。(这里配合 dummy 节点食用更佳)。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
ListNode* removeNthFromEnd(ListNode* head, int n) {
    ListNode* dummy = new ListNode(0, head); // 使用哨兵节点简化边界情况
    ListNode* fast = dummy;
    ListNode* slow = dummy;

    // 让 fast 先走 n 步
    for (int i = 0; i < n; ++i) {
        fast = fast->next;
    }

    // 然后 slow 和 fast 一起走，直到 fast 到达链表末尾
    while (fast->next != nullptr) {
        fast = fast->next;
        slow = slow->next;
    }

    // 此时 slow 停在倒数第 n+1 个节点上，删除它的下一个节点
    slow->next = slow->next->next;
    // 返回新的头节点
    ListNode* newHead = dummy->next;
    delete dummy; // 释放哨兵节点
    return newHead;
}

LRU

LRU (Least Recently Used) 缓存是一种常用的缓存淘汰策略，用于在缓存容量有限时，移除最久未使用的数据。LRU 缓存通常使用哈希表和双向链表结合实现，以支持高效的插入、删除和访问操作。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
class LRUCache {
    struct Node{
        int key;
        int val;
        Node* next;
        Node* prev;

        Node(int k, int v):key(k), val(v), next(nullptr), prev(nullptr){}
    };
    unordered_map<int, Node*> map;
    Node* head;
    Node* tail;
    int capacity;

    void remove(Node* node){
        node->prev->next = node->next;
        node->next->prev = node->prev;
    }

    void add(Node* node){
        node->next = head->next;
        head->next->prev = node;
        node->prev = head;
        head->next = node;
    }
    void changeFirst(Node* node){
        remove(node);
        add(node);
    }
public:
    LRUCache(int capacity):capacity(capacity) {
        head = new Node(-1,-1);
        tail = new Node(-1,-1);
        head->next = tail;
        tail->prev = head;
    }
    
    int get(int key) {
        if(!map.contains(key)) return -1;
        Node* node = map[key];
        changeFirst(node);
        return node->val;
    }
    
    void put(int key, int value) {
        if(map.contains(key)){
            Node* node = map[key];
            node->val = value;
            changeFirst(node);
        }else{
            if(map.size()==capacity){
                Node* last = tail->prev;
                remove(last);
                map.erase(last->key);
            }
            Node* node = new Node(key, value);
            add(node);
            map[key] = node;
        }
    }
};

线程安全的 LRUCache 则可以使用互斥锁 (mutex) 来保护共享数据结构，确保在多线程环境下的正确性。 此外, 还可以将指针改为智能指针来自动管理内存，防止内存泄漏。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68

class LRUCache{
    struct Node{
        int key;
        int val;
        shared_ptr<Node> next;
        weak_ptr<Node> prev;

        Node(int k, int v): key(k), val(v), next(nullptr), prev(nullptr){}
    };

    int capacity;
    unordered_map<int, shared_ptr<Node>> map;
    shared_ptr<Node> head;
    shared_ptr<Node> tail;
    mutex mtx;

    void remove(shared_ptr<Node> node){
        node->next->prev = node->prev;      // 而这个 weak_ptr 只是赋值, 不需要 lock() 
        node->prev.lock()->next = node->next;  // 注意 weak_ptr 如果要访问资源需要 lock() 转换为 shared_ptr
    }

    void add(shared_ptr<Node> node){
        node->next = head->next;
        node->next->prev = node;
        head->next = node;
        node->prev = head;
    }

    void remove_add(shared_ptr<Node> node){
        remove(node);
        add(node);
    }

public:
    LRUCache(int capacity): capacity(capacity){
        head = make_shared<Node>(-1,-1);
        tail = make_shared<Node>(-1,-1);
        head->next = tail;
        tail->prev = head;
    }

    int get(int key){
        lock_guard<mutex> lk(mtx);
        if(!map.count(key)) return -1;
        shared_ptr<Node> node = map[key];
        remove_add(node);
        return node->val;
    }

    void put(int key, int value){
        lock_guard<mutex> lk(mtx);
        if(map.count(key)){
            shared_ptr<Node> node = map[key];
            node->val = value;
            remove_add(node);
        }else{
            if(capacity==map.size()){
                shared_ptr<Node> last = tail->prev.lock();
                map.erase(last->key);
                remove(last);
            } // 自动释放, 因为使用了智能指针
            shared_ptr<Node> node = make_shared<Node>(key, value);
            map[key] = node;
            add(node);
        }
    }
};

上面的示例展示了一个线程安全且使用智能指针管理内存的 LRUCache 实现。但是，在高并发场景下，使用单一互斥锁可能会成为性能瓶颈。为了提高并发性能，还可以考虑的是使用分段锁 (Segmented Locking)来优化锁的粒度，从而允许更多的并发访问。

读写锁在这里并不适用, 因为 LRU 缓存的每次 get 操作都会修改链表结构 (将访问的节点移动到头部), 因此即使是读取操作也需要写锁。

下面是一个使用分段锁的 LRUCache 示例：

把缓存拆成 N 段（shard） 每段有自己独立的 map + 链表 + mutex 不同段的 get/put 可以同时操作，互不阻塞

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
#include <iostream>
#include <vector>
#include <mutex>
#include <unordered_map>
#include <functional> // for std::hash

// 1. 基础的 LRU Cache (使用 std::mutex)
// 代码与之前最基础的线程安全版本一致，为了节省篇幅，这里简化展示
class LRUCacheShard {
    struct Node {
        int key, val;
        Node *next, *prev;
        Node(int k, int v) : key(k), val(v), next(nullptr), prev(nullptr) {}
    };
    std::unordered_map<int, Node*> map;
    Node *head, *tail;
    int capacity;
    std::mutex mtx; // 每个分片一把锁

    void remove(Node* node) {
        node->prev->next = node->next;
        node->next->prev = node->prev;
    }
    void add(Node* node) {
        node->next = head->next;
        head->next->prev = node;
        node->prev = head;
        head->next = node;
    }
    void changeFirst(Node* node) {
        remove(node);
        add(node);
    }

public:
    LRUCacheShard(int cap) : capacity(cap) {
        head = new Node(-1, -1);
        tail = new Node(-1, -1);
        head->next = tail;
        tail->prev = head;
    }
    ~LRUCacheShard() {
        Node* curr = head;
        while(curr){ Node* t=curr; curr=curr->next; delete t; }
    }

    int get(int key) {
        std::lock_guard<std::mutex> lock(mtx);
        auto it = map.find(key);
        if (it == map.end()) return -1;
        changeFirst(it->second);
        return it->second->val;
    }

    void put(int key, int value) {
        std::lock_guard<std::mutex> lock(mtx);
        auto it = map.find(key);
        if (it != map.end()) {
            it->second->val = value;
            changeFirst(it->second);
            return;
        }
        if (map.size() >= capacity) {
            Node* last = tail->prev;
            remove(last);
            map.erase(last->key);
            delete last;
        }
        Node* node = new Node(key, value);
        add(node);
        map[key] = node;
    }
};

// 2. 分段 LRU Cache 容器
class ShardedLRUCache {
private:
    std::vector<LRUCacheShard*> shards; // 分片数组
    int num_shards;                     // 分片数量
    std::hash<int> hasher;              // 哈希函数

    // 计算 Key 属于哪个分片
    int getShardIdx(int key) {
        return hasher(key) % num_shards;
    }

public:
    // total_capacity: 总容量
    // num_shards: 分片数量（建议设为 2 的幂，如 16, 64）
    ShardedLRUCache(int total_capacity, int num_shards) : num_shards(num_shards) {
        int cap_per_shard = (total_capacity + num_shards - 1) / num_shards; // 计算每个分片的容量
        for (int i = 0; i < num_shards; ++i) {
            shards.push_back(new LRUCacheShard(cap_per_shard));  // 初始化每个分片
        }
    }

    ~ShardedLRUCache() {
        for (auto shard : shards) delete shard;
    }

    int get(int key) {
        // 只需要锁住特定的分片，其他分片依然可以并发访问
        return shards[getShardIdx(key)]->get(key);
    }

    void put(int key, int value) {
        shards[getShardIdx(key)]->put(key, value);
    }
};

LFU

LFU 也是一种缓存淘汰策略, 它会移除使用频率最低的数据. 实现 LFU 缓存通常需要维护一个频率表, 记录每个键的使用频率, 并结合哈希表和双向链表来支持高效的插入、删除和访问操作. (也就是我们需要一个哈希表来存储键到节点的映射, 另一个哈希表来存储频率到节点列表的映射)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
class LFUCache {
    struct Node{
        int key;
        int val;
        int freq;
        Node* next;
        Node* prev;
        Node(int k,int v): key(k), val(v), freq(1), next(nullptr), prev(nullptr){}
    };
    struct FreqList{
        Node* head;
        Node* tail;
        FreqList(){
            head = new Node(-1,-1);
            tail = new Node(-1,-1);
            head->next = tail;
            tail->prev = head;
        }

        bool empty(){
            return head->next==tail? true:false;
        }

        void remove(Node* node){
            node->next->prev = node->prev;
            node->prev->next = node->next;
        }
        void add(Node* node){
            node->next = head->next;
            node->prev = head;
            head->next = node;
            node->next->prev = node;
        }
    };
    int min_freq;
    int capacity;
    unordered_map<int, Node*> key_map;
    unordered_map<int, FreqList> freq_map;

public:
    LFUCache(int capacity): capacity(capacity), min_freq(1) {}
    
    int get(int key) {
        if(key_map.count(key)==0) return -1;

        Node* node = key_map[key];
        int old_freq = node->freq;
        int new_freq = old_freq+1;
        node->freq = new_freq;

        freq_map[old_freq].remove(node);
        freq_map[new_freq].add(node);
        if(freq_map[old_freq].empty() && old_freq==min_freq) min_freq = new_freq;

        return node->val;
    }
    
    void put(int key, int value) {
        if(key_map.count(key)!=0){
            Node* node = key_map[key];
            int old_freq = node->freq;
            int new_freq = old_freq+1;
            node->freq = new_freq;
            node->val = value;

            freq_map[old_freq].remove(node);
            freq_map[new_freq].add(node);
            if(freq_map[old_freq].empty()&&old_freq==min_freq) min_freq = new_freq;
            
        }else{
            if(capacity==key_map.size()){
                Node* old_node = freq_map[min_freq].tail->prev;
                freq_map[min_freq].remove(old_node);
                key_map.erase(old_node->key);
            }
            Node* node = new Node(key, value);
            key_map[key] = node;
            freq_map[1].add(node);
            min_freq = 1;
        }
    }
};

```

On this page
  1. 链表
    1. 两个黄金问题
    2. 遍历链表
    3. 链表排序
    4. 反转链表
    5. LRU
      1. LFU