1
template <typename T>
2
class SinglyLinkedList {
3
    struct Node {
4
        T     data;
5
        Node* next = nullptr;
6

7
        Node(const T& val, Node* n = nullptr) : data(val), next(n) {}
8
    };
9

10
    Node*       _head = nullptr;
11
    std::size_t _size = 0;
12

13
public:
14
    ~SinglyLinkedList() { clear(); }
15

16
    // ========== 头部操作 O(1) ==========
17
    void push_front(const T& val) {
18
        _head = new Node(val, _head);
19
        ++_size;
20
    }
21

22
    void pop_front() {
23
        if (!_head) return;
24
        Node* old = _head;
25
        _head = _head->next;
26
        delete old;
27
        --_size;
28
    }
29

30
    T& front() { return _head->data; }
31

32
    // ========== 在指定节点后插入 O(1) ==========
33
    void insert_after(Node* pos, const T& val) {
34
        if (!pos) return;
35
        pos->next = new Node(val, pos->next);
36
        ++_size;
37
    }
38

39
    // ========== 删除指定节点后的节点 O(1) ==========
40
    void erase_after(Node* pos) {
41
        if (!pos || !pos->next) return;
42
        Node* target = pos->next;
43
        pos->next = target->next;
44
        delete target;
45
        --_size;
46
    }
47

48
    // ========== 查找 O(n) ==========
49
    Node* find(const T& val) {
50
        Node* cur = _head;
51
        while (cur) {
52
            if (cur->data == val) return cur;
53
            cur = cur->next;
54
        }
55
        return nullptr;
56
    }
57

58
    // ========== 反转 O(n) ==========
59
    void reverse() {
60
        Node* prev = nullptr;
61
        Node* curr = _head;
62
        while (curr) {
63
            Node* next = curr->next;
64
            curr->next = prev;
65
            prev = curr;
66
            curr = next;
67
        }
68
        _head = prev;
69
    }
70

71
    void clear() {
72
        while (_head) pop_front();
73
    }
74

75
    std::size_t size() const { return _size; }
76
    bool empty() const { return _head == nullptr; }
77
};

1
template <typename T>
2
class List {
3
    struct Node {
4
        T     data;
5
        Node* prev;
6
        Node* next;
7
        Node() : prev(this), next(this) {}  // 哨兵节点自环
8
        Node(const T& val, Node* p, Node* n) : data(val), prev(p), next(n) {}
9
    };
10

11
    Node        _sentinel;  // 哨兵节点（不存数据）
12
    std::size_t _size = 0;
13

14
    // 核心：在 pos 之前插入
15
    Node* _insert(Node* pos, const T& val) {
16
        Node* node = new Node(val, pos->prev, pos);
17
        pos->prev->next = node;  // 前驱的 next 指向新节点
18
        pos->prev = node;        // pos 的 prev 指向新节点
19
        ++_size;
20
        return node;
21
    }
22

23
    // 核心：删除 pos 节点
24
    Node* _erase(Node* pos) {
25
        Node* next = pos->next;
26
        pos->prev->next = pos->next;  // 前驱跳过 pos
27
        pos->next->prev = pos->prev;  // 后继跳过 pos
28
        delete pos;
29
        --_size;
30
        return next;
31
    }
32

33
public:
34
    // begin/end 利用哨兵形成逻辑区间
35
    // sentinel.next = 第一个元素
36
    // sentinel 自身 = end()（past-the-end）
37

38
    void push_back(const T& val)  { _insert(&_sentinel, val); }
39
    void push_front(const T& val) { _insert(_sentinel.next, val); }
40
    void pop_back()  { _erase(_sentinel.prev); }
41
    void pop_front() { _erase(_sentinel.next); }
42

43
    T& front() { return _sentinel.next->data; }
44
    T& back()  { return _sentinel.prev->data; }
45

46
    std::size_t size() const { return _size; }
47
    bool empty() const { return _size == 0; }
48

49
    // splice: 把另一个链表的节点 O(1) 移过来（不拷贝数据！）
50
    // 这是 std::list 最强大的操作之一
51
    void splice(Node* pos, List& other, Node* it) {
52
        // 从 other 摘下 it
53
        it->prev->next = it->next;
54
        it->next->prev = it->prev;
55
        --other._size;
56

57
        // 接到 pos 之前
58
        it->prev = pos->prev;
59
        it->next = pos;
60
        pos->prev->next = it;
61
        pos->prev = it;
62
        ++_size;
63
    }
64

65
    ~List() {
66
        while (!empty()) pop_front();
67
    }
68
};

1
// forward_list 相比 list 的差异：
2
// - 只有 next 指针，没有 prev → 每节点省 8 字节
3
// - 没有 size() 方法！（为了省一个 size_t 成员）
4
// - 只有 push_front / pop_front / insert_after / erase_after
5
// - 没有 push_back（单链表尾插需要遍历到尾部 O(n)）
6

7
std::forward_list<int> flist = {1, 2, 3, 4, 5};
8

9
// 在头部插入
10
flist.push_front(0);               // [0, 1, 2, 3, 4, 5]
11

12
// 在某个位置之后插入（注意 API 是 _after）
13
auto it = flist.begin();
14
std::advance(it, 2);               // it 指向 2
15
flist.insert_after(it, 99);        // [0, 1, 2, 99, 3, 4, 5]
16

17
// 删除某个位置之后的元素
18
flist.erase_after(it);             // [0, 1, 2, 3, 4, 5]
19

20
// 获取大小需要手动算（标准库不提供 size()）
21
auto count = std::distance(flist.begin(), flist.end()); // O(n)

1
// ========== 侵入式链表的 Hook ==========
2
struct IntrusiveListHook {
3
    IntrusiveListHook* prev = nullptr;
4
    IntrusiveListHook* next = nullptr;
5

6
    bool is_linked() const { return prev != nullptr; }
7

8
    // 从当前链表中脱离
9
    void unlink() {
10
        if (prev) prev->next = next;
11
        if (next) next->prev = prev;
12
        prev = next = nullptr;
13
    }
14
};
15

16
// ========== 侵入式链表容器 ==========
17
template <typename T, IntrusiveListHook T::*HookPtr>
18
class IntrusiveList {
19
    IntrusiveListHook _sentinel;
20
    std::size_t       _size = 0;
21

22
    // 从 hook 指针反推出宿主对象指针
23
    static T* _to_object(IntrusiveListHook* hook) {
24
        // 计算 hook 成员在 T 中的偏移，反向得到 T*
25
        // 等价于 Linux 内核的 container_of 宏
26
        static constexpr auto offset =
27
            reinterpret_cast<std::size_t>(
28
                &(static_cast<T*>(nullptr)->*HookPtr));
29
        return reinterpret_cast<T*>(
30
            reinterpret_cast<char*>(hook) - offset);
31
    }
32

33
    IntrusiveListHook* _hook(T* obj) {
34
        return &(obj->*HookPtr);
35
    }
36

37
public:
38
    IntrusiveList() {
39
        _sentinel.prev = &_sentinel;
40
        _sentinel.next = &_sentinel;
41
    }
42

43
    void push_back(T* obj) {
44
        auto* hook = _hook(obj);
45
        hook->prev = _sentinel.prev;
46
        hook->next = &_sentinel;
47
        _sentinel.prev->next = hook;
48
        _sentinel.prev = hook;
49
        ++_size;
50
    }
51

52
    void push_front(T* obj) {
53
        auto* hook = _hook(obj);
54
        hook->next = _sentinel.next;
55
        hook->prev = &_sentinel;
56
        _sentinel.next->prev = hook;
57
        _sentinel.next = hook;
58
        ++_size;
59
    }
60

61
    // O(1) 移除——对象自己知道自己在链表中的位置
62
    void remove(T* obj) {
63
        auto* hook = _hook(obj);
64
        hook->unlink();
65
        --_size;
66
    }
67

68
    T* front() { return _to_object(_sentinel.next); }
69
    T* back()  { return _to_object(_sentinel.prev); }
70

71
    bool empty() const { return _size == 0; }
72
    std::size_t size() const { return _size; }
73

74
    // 简易迭代器
75
    struct Iterator {
76
        IntrusiveListHook* hook;
77
        T& operator*() { return *_to_object(hook); }
78
        Iterator& operator++() { hook = hook->next; return *this; }
79
        bool operator!=(const Iterator& o) const { return hook != o.hook; }
80
    };
81

82
    Iterator begin() { return {_sentinel.next}; }
83
    Iterator end()   { return {&_sentinel}; }
84
};

1
struct GameObject {
2
    int         id;
3
    float       x, y;
4
    std::string name;
5

6
    // 嵌入 hook —— 可以同时属于多个链表！
7
    IntrusiveListHook scene_link;   // 场景链表
8
    IntrusiveListHook render_link;  // 渲染链表
9
    IntrusiveListHook physics_link; // 物理链表
10
};
11

12
// 场景中的所有对象
13
IntrusiveList<GameObject, &GameObject::scene_link> scene_objects;
14
// 需要渲染的对象
15
IntrusiveList<GameObject, &GameObject::render_link> render_list;
16
// 需要物理更新的对象
17
IntrusiveList<GameObject, &GameObject::physics_link> physics_list;
18

19
// 一个对象可以同时存在于三个链表中
20
auto* obj = new GameObject{1, 10.0f, 20.0f, "Enemy"};
21
scene_objects.push_back(obj);
22
render_list.push_back(obj);
23
physics_list.push_back(obj);
24

25
// 从场景中移除——O(1)，不影响其他链表
26
scene_objects.remove(obj);

1
struct ListNode {
2
    int val;
3
    ListNode* next;
4
    ListNode(int x) : val(x), next(nullptr) {}
5
};
6

7
// 方法一：迭代（推荐）
8
ListNode* reverseList(ListNode* head) {
9
    ListNode* prev = nullptr;
10
    ListNode* curr = head;
11
    while (curr) {
12
        ListNode* next = curr->next;  // 1. 暂存下一个
13
        curr->next = prev;            // 2. 反转指针
14
        prev = curr;                  // 3. prev 前进
15
        curr = next;                  // 4. curr 前进
16
    }
17
    return prev;  // prev 现在是新头
18
}
19
// 时间 O(n), 空间 O(1)
20

21
// 方法二：递归（理解递归思维）
22
ListNode* reverseListRecursive(ListNode* head) {
23
    if (!head || !head->next) return head;
24

25
    ListNode* newHead = reverseListRecursive(head->next);
26
    // 此时 head->next 是反转后子链表的尾节点
27
    head->next->next = head;  // 让尾节点指回 head
28
    head->next = nullptr;     // head 变成新尾
29
    return newHead;
30
}
31
// 时间 O(n), 空间 O(n)（递归栈）

1
ListNode* reverseBetween(ListNode* head, int left, int right) {
2
    ListNode dummy(0);
3
    dummy.next = head;
4

5
    // 1. 找到反转区间的前一个节点
6
    ListNode* pre = &dummy;
7
    for (int i = 1; i < left; ++i) {
8
        pre = pre->next;
9
    }
10

11
    // 2. 头插法反转区间
12
    // pre -> [left] -> [left+1] -> ... -> [right] -> after
13
    ListNode* curr = pre->next;
14
    for (int i = 0; i < right - left; ++i) {
15
        ListNode* next = curr->next;
16
        curr->next = next->next;     // curr 跳过 next
17
        next->next = pre->next;      // next 插到区间最前面
18
        pre->next = next;            // pre 指向新的区间头
19
    }
20

21
    return dummy.next;
22
}
23
// 时间 O(n), 空间 O(1)

1
ListNode* detectCycle(ListNode* head) {
2
    ListNode* slow = head;
3
    ListNode* fast = head;
4

5
    // 第一阶段：快慢指针找相遇点
6
    while (fast && fast->next) {
7
        slow = slow->next;
8
        fast = fast->next->next;
9
        if (slow == fast) break;
10
    }
11
    if (!fast || !fast->next) return nullptr;  // 无环
12

13
    // 第二阶段：一个从 head 出发，一个从相遇点出发，都走 1 步
14
    // 再次相遇的地方就是环入口
15
    slow = head;
16
    while (slow != fast) {
17
        slow = slow->next;
18
        fast = fast->next;
19
    }
20
    return slow;
21
}

1
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
2
    ListNode dummy(0);
3
    ListNode* tail = &dummy;
4

5
    while (l1 && l2) {
6
        if (l1->val <= l2->val) {
7
            tail->next = l1;
8
            l1 = l1->next;
9
        } else {
10
            tail->next = l2;
11
            l2 = l2->next;
12
        }
13
        tail = tail->next;
14
    }
15
    tail->next = l1 ? l1 : l2;  // 接上剩余部分
16

17
    return dummy.next;
18
}
19
// 时间 O(n+m), 空间 O(1)

1
ListNode* mergeKLists(std::vector<ListNode*>& lists) {
2
    // 最小堆：每次取 K 个链表头中最小的
3
    auto cmp = [](ListNode* a, ListNode* b) { return a->val > b->val; };
4
    std::priority_queue<ListNode*, std::vector<ListNode*>, decltype(cmp)> pq(cmp);
5

6
    // 初始化：把每个链表的头节点入堆
7
    for (auto* head : lists) {
8
        if (head) pq.push(head);
9
    }
10

11
    ListNode dummy(0);
12
    ListNode* tail = &dummy;
13

14
    while (!pq.empty()) {
15
        ListNode* smallest = pq.top();
16
        pq.pop();
17

18
        tail->next = smallest;
19
        tail = tail->next;
20

21
        if (smallest->next) {
22
            pq.push(smallest->next);  // 把下一个节点入堆
23
        }
24
    }
25

26
    return dummy.next;
27
}
28
// 时间 O(N log K)，N 是所有节点总数，K 是链表数
29
// 空间 O(K)（堆的大小）

1
class LRUCache {
2
    struct Node {
3
        int key, value;
4
        Node* prev = nullptr;
5
        Node* next = nullptr;
6
        Node(int k, int v) : key(k), value(v) {}
7
    };
8

9
    int _capacity;
10
    std::unordered_map<int, Node*> _map;  // key → Node*
11
    Node _head{0, 0};  // 虚拟头
12
    Node _tail{0, 0};  // 虚拟尾
13

14
    // 把节点移到头部（标记为最近使用）
15
    void _move_to_front(Node* node) {
16
        _remove(node);
17
        _add_front(node);
18
    }
19

20
    // 从链表中摘除节点
21
    void _remove(Node* node) {
22
        node->prev->next = node->next;
23
        node->next->prev = node->prev;
24
    }
25

26
    // 在虚拟头之后插入（最近使用的位置）
27
    void _add_front(Node* node) {
28
        node->next = _head.next;
29
        node->prev = &_head;
30
        _head.next->prev = node;
31
        _head.next = node;
32
    }
33

34
public:
35
    LRUCache(int capacity) : _capacity(capacity) {
36
        _head.next = &_tail;
37
        _tail.prev = &_head;
38
    }
39

40
    int get(int key) {
41
        auto it = _map.find(key);
42
        if (it == _map.end()) return -1;
43

44
        _move_to_front(it->second);  // 标记为最近使用
45
        return it->second->value;
46
    }
47

48
    void put(int key, int value) {
49
        auto it = _map.find(key);
50
        if (it != _map.end()) {
51
            it->second->value = value;
52
            _move_to_front(it->second);
53
            return;
54
        }
55

56
        // 容量满了，淘汰最久未使用的（链表尾部）
57
        if (_map.size() == _capacity) {
58
            Node* lru = _tail.prev;
59
            _remove(lru);
60
            _map.erase(lru->key);
61
            delete lru;
62
        }
63

64
        // 插入新节点
65
        Node* node = new Node(key, value);
66
        _add_front(node);
67
        _map[key] = node;
68
    }
69

70
    ~LRUCache() {
71
        Node* cur = _head.next;
72
        while (cur != &_tail) {
73
            Node* next = cur->next;
74
            delete cur;
75
            cur = next;
76
        }
77
    }
78
};
79
// get: O(1), put: O(1)

1
ListNode* reverseKGroup(ListNode* head, int k) {
2
    ListNode dummy(0);
3
    dummy.next = head;
4
    ListNode* group_prev = &dummy;  // 每组的前驱
5

6
    while (true) {
7
        // 1. 检查剩余节点是否 >= k 个
8
        ListNode* kth = group_prev;
9
        for (int i = 0; i < k; ++i) {
10
            kth = kth->next;
11
            if (!kth) return dummy.next;  // 不足 k 个，结束
12
        }
13

14
        ListNode* group_next = kth->next;  // 下一组的起点
15

16
        // 2. 反转当前组 [group_prev->next, kth]
17
        ListNode* prev = group_next;  // 反转后尾部接上下一组
18
        ListNode* curr = group_prev->next;
19
        while (curr != group_next) {
20
            ListNode* next = curr->next;
21
            curr->next = prev;
22
            prev = curr;
23
            curr = next;
24
        }
25

26
        // 3. 拼接：更新前驱和后继
27
        ListNode* new_group_first = prev;      // 反转后的组头 = kth
28
        ListNode* new_group_last = group_prev->next;  // 反转后的组尾 = 原组头
29

30
        group_prev->next = new_group_first;
31
        group_prev = new_group_last;  // 移动到下一组的前驱
32
    }
33
}
34
// 时间 O(n), 空间 O(1)

1
初始: dummy → 1 → 2 → 3 → 4 → 5
2
                  ↑       ↑
3
               group_prev=dummy, kth=2
4

5
第一组反转 [1,2]:
6
  dummy → 2 → 1 → 3 → 4 → 5
7
               ↑
8
            group_prev=1
9

10
第二组反转 [3,4]:
11
  dummy → 2 → 1 → 4 → 3 → 5
12
                        ↑
13
                     group_prev=3
14

15
不足 k=2 个，结束：
16
  结果: 2 → 1 → 4 → 3 → 5

1
struct RandomNode {
2
    int val;
3
    RandomNode* next;
4
    RandomNode* random;
5
    RandomNode(int x) : val(x), next(nullptr), random(nullptr) {}
6
};
7

8
RandomNode* copyRandomList(RandomNode* head) {
9
    if (!head) return nullptr;
10

11
    // key = 原节点, value = 新节点
12
    std::unordered_map<RandomNode*, RandomNode*> map;
13

14
    // 第一遍：创建所有新节点
15
    RandomNode* curr = head;
16
    while (curr) {
17
        map[curr] = new RandomNode(curr->val);
18
        curr = curr->next;
19
    }
20

21
    // 第二遍：连接 next 和 random
22
    curr = head;
23
    while (curr) {
24
        map[curr]->next = map[curr->next];
25
        map[curr]->random = map[curr->random];
26
        curr = curr->next;
27
    }
28

29
    return map[head];
30
}
31
// 时间 O(n), 空间 O(n)

1
RandomNode* copyRandomList_O1(RandomNode* head) {
2
    if (!head) return nullptr;
3

4
    // 第一步：在每个原节点后面插入一个克隆节点
5
    // 1 → 1' → 2 → 2' → 3 → 3'
6
    RandomNode* curr = head;
7
    while (curr) {
8
        RandomNode* clone = new RandomNode(curr->val);
9
        clone->next = curr->next;
10
        curr->next = clone;
11
        curr = clone->next;
12
    }
13

14
    // 第二步：设置克隆节点的 random 指针
15
    curr = head;
16
    while (curr) {
17
        if (curr->random) {
18
            curr->next->random = curr->random->next;  // 精髓！
19
        }
20
        curr = curr->next->next;
21
    }
22

23
    // 第三步：拆分两个链表
24
    RandomNode dummy(0);
25
    RandomNode* clone_tail = &dummy;
26
    curr = head;
27
    while (curr) {
28
        clone_tail->next = curr->next;
29
        clone_tail = clone_tail->next;
30
        curr->next = curr->next->next;  // 恢复原链表
31
        curr = curr->next;
32
    }
33

34
    return dummy.next;
35
}
36
// 时间 O(n), 空间 O(1)

1
// 归并排序（自底向上，O(1) 空间）
2
ListNode* sortList(ListNode* head) {
3
    if (!head || !head->next) return head;
4

5
    // 计算链表长度
6
    int len = 0;
7
    for (auto* p = head; p; p = p->next) ++len;
8

9
    ListNode dummy(0);
10
    dummy.next = head;
11

12
    // 步长从 1 开始倍增
13
    for (int step = 1; step < len; step <<= 1) {
14
        ListNode* prev = &dummy;
15
        ListNode* curr = dummy.next;
16

17
        while (curr) {
18
            // 切出第一段（长度 step）
19
            ListNode* left = curr;
20
            ListNode* right = _split(left, step);
21

22
            // 切出第二段（长度 step）
23
            curr = _split(right, step);
24

25
            // 合并两段，接到 prev 后面
26
            prev = _merge(left, right, prev);
27
        }
28
    }
29
    return dummy.next;
30
}
31

32
// 从 head 开始切出前 n 个节点，返回剩余部分的头
33
static ListNode* _split(ListNode* head, int n) {
34
    for (int i = 1; head && i < n; ++i) {
35
        head = head->next;
36
    }
37
    if (!head) return nullptr;
38
    ListNode* rest = head->next;
39
    head->next = nullptr;  // 切断
40
    return rest;
41
}
42

43
// 合并两个有序链表，接到 prev 后面，返回合并后的尾节点
44
static ListNode* _merge(ListNode* l1, ListNode* l2, ListNode* prev) {
45
    while (l1 && l2) {
46
        if (l1->val <= l2->val) {
47
            prev->next = l1;
48
            l1 = l1->next;
49
        } else {
50
            prev->next = l2;
51
            l2 = l2->next;
52
        }
53
        prev = prev->next;
54
    }
55
    prev->next = l1 ? l1 : l2;
56
    while (prev->next) prev = prev->next;  // 走到尾部
57
    return prev;
58
}
59
// 时间 O(n log n), 空间 O(1)

1
template <typename T, std::size_t BlockCount>
2
class PoolAllocator {
3
    union Block {
4
        T      object;
5
        Block* next;   // 空闲时复用对象内存存指针！
6

7
        Block() {}     // 不要默认构造 T
8
        ~Block() {}    // 不要析构 T
9
    };
10

11
    std::array<Block, BlockCount> _pool;
12
    Block* _free_head = nullptr;   // 空闲链表头
13

14
public:
15
    PoolAllocator() {
16
        // 初始化空闲链表：所有 block 串成单链表
17
        for (std::size_t i = 0; i < BlockCount - 1; ++i) {
18
            _pool[i].next = &_pool[i + 1];
19
        }
20
        _pool[BlockCount - 1].next = nullptr;
21
        _free_head = &_pool[0];
22
    }
23

24
    // 分配一个对象 —— O(1)，零系统调用
25
    template <typename... Args>
26
    T* allocate(Args&&... args) {
27
        if (!_free_head) return nullptr;  // 池满
28

29
        Block* block = _free_head;
30
        _free_head = _free_head->next;
31

32
        // 在空闲块上 placement new 构造对象
33
        return new (&block->object) T(std::forward<Args>(args)...);
34
    }
35

36
    // 释放一个对象 —— O(1)，零系统调用
37
    void deallocate(T* ptr) {
38
        ptr->~T();  // 手动析构
39

40
        // 把释放的块接回空闲链表头
41
        Block* block = reinterpret_cast<Block*>(ptr);
42
        block->next = _free_head;
43
        _free_head = block;
44
    }
45

46
    std::size_t available() const {
47
        std::size_t count = 0;
48
        for (Block* b = _free_head; b; b = b->next) ++count;
49
        return count;
50
    }
51
};