题目

编写程序，演示非连续双向环形链表 std::list 的核心独门神技——splice() 节点嫁接。演示将一个链表中的单个节点、连续区间乃至整条链表，在无需进行任何元素拷贝、移动或内存分配（new/delete）的前提下，纯靠常数级 O(1) 指针重定向，瞬间嫁接到另一个链表的指定位置。

输入格式：无需外部输入。

输出格式：输出嫁接操作前后源链表与目标链表的节点变化及地址恒定性。

数据范围与约定：双向循环链表指针操作与常数级拼接。

思路与算法

1. splice 的零拷贝本质
splice 是 std::list 区别于所有顺序容器的杀手级功能。它仅仅修改前驱和后继指针（prev 与 next），节点的实际堆内存在整个过程中保持原位不动。

2. 迭代器绝对不失效
被 splice 转移的元素，其迭代器、指针与引用在操作完成后依然完全有效，只是逻辑上归属于新的 list 容器管辖。

3. 手写 LRU 的核心基石
高性能 LRU Cache 淘汰器正是利用 list.splice(list.begin(), list, it)，将刚刚命中的缓存节点在 O(1) 时间内移到链表头部的。

完整程序

#include <iostream>
#include <list>

void printList(const std::list<int>& lst, const std::string& name) {
    std::cout << name << " (size: " << lst.size() << "): ";
    for (int x : lst) std::cout << x << " ";
    std::cout << "\n";
}

int main() {
    std::list<int> listA = {1, 2, 3};
    std::list<int> listB = {10, 20, 30, 40};

    std::cout << "--- 嫁接前初始状态 ---\n";
    printList(listA, "List A");
    printList(listB, "List B");

    // 1. 获取 listB 中节点 20 的迭代器，并记录物理地址
    auto it20 = ++listB.begin();
    const int* addr20 = &(*it20);
    std::cout << "\n关注节点 20 已记录其稳定堆地址\n";

    // 2. 将 listB 中的单节点 20 嫁接到 listA 的头部
    listA.splice(listA.begin(), listB, it20);

    std::cout << "\n--- 执行 listA.splice(listA.begin(), listB, it20) 之后 ---\n";
    printList(listA, "List A (20 移入头部)");
    printList(listB, "List B (20 已消失)");
    std::cout << "移入 List A 后节点 20 地址是否仍是原地址: "
              << std::boolalpha << (&(*listA.begin()) == addr20) << " (零拷贝)\n";

    // 3. 将 listB 剩余所有节点整体嫁接到 listA 尾部
    listA.splice(listA.end(), listB);
    std::cout << "\n--- 将 List B 整表嫁接至 List A 末尾 ---\n";
    printList(listA, "List A");
    printList(listB, "List B (完全变为空表)");

    return 0;
}

运行示例

输出：

--- 嫁接前初始状态 ---
List A (size: 3): 1 2 3 
List B (size: 4): 10 20 30 40 

关注节点 20 已记录其稳定堆地址

--- 执行 listA.splice(listA.begin(), listB, it20) 之后 ---
List A (20 移入头部) (size: 4): 20 1 2 3 
List B (20 已消失) (size: 3): 10 30 40 
移入 List A 后节点 20 地址是否仍是原地址: true (零拷贝)

--- 将 List B 整表嫁接至 List A 末尾 ---
List A (size: 7): 20 1 2 3 10 30 40 
List B (完全变为空表) (size: 0):