环形链表检测、数组交集与随机链表复制实战

1. 去重：利用 std::set 自动去重的特性，将两个数组转换为集合。
2. 查找：遍历其中一个集合的元素，检查是否存在于另一个集合中。

此外，还有一种基于对比算法的思路（双指针），适用于有序数据，效率更高。例如在云端存储同步场景中，对比本地文件与云端文件列表时，常利用此类逻辑判断哪些文件需要更新或导入。

代码实现

基础解法（Set + Count）

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        // 去重
        std::set<int> s1(nums1.begin(), nums1.end());
        std::set<int> s2(nums2.begin(), nums2.end());
        vector<int> v;
        // 将一个数组中的值依次到另一个数组中查找
        for(auto e : s1) {
            if(s2.count(e)) {
                v.push_back(e); // 在另一个数组中插入到一个容器中
            }
        }
        return v;
    }
};

优化解法（对比算法）

由于 std::set 遍历是有序的，我们可以直接比较两个集合的元素，小的移动指针，相等的即为交集。

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        std::set<int> s1(nums1.begin(), nums1.end());
        std::set<int> s2(nums2.begin(), nums2.end());
        vector<int> ret;
        auto it1 = s1.begin();
        auto it2 = s2.begin();
        // 因为 set 遍历是有序的，有序值，依次比较，小的++，相等的就是交集
        while(it1 != s1.end() && it2 != s2.end()) {
            if(*it1 < *it2) {
                it1++;
            } else if(*it1 > *it2) {
                it2++;
            } else {
                ret.push_back(*it1);
                it1++;
                it2++;
            }
        }
        return ret;
    }
};

随机链表的复制

题目描述

给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random，该指针可以指向链表中的任何节点或空节点。构造这个链表的深拷贝。深拷贝应该正好由 n 个全新节点组成，其中新节点的 next 指针和 random 指针也都应指向复制链表中的新节点。

解题思路

这道题的难点在于 random 指针的拷贝。原链表和拷贝出的链表之间没有天然联系，直接拷贝会导致 random 无法正确映射。

方法一：C 语言穿插节点法（空间复杂度 O(1)）

核心思想是在原链表每个节点后插入一个拷贝节点，这样原节点和新节点就有了物理上的相邻关系。通过 pcur->random->next 即可找到对应的新节点。

/**
 * Definition for a Node.
 * struct Node {
 *     int val;
 *     struct Node *next;
 *     struct Node *random;
 * };
 */
typedef struct Node Node;

// 构造一个新节点
Node* buyNode(int x) {
    Node* newnode = (Node*)malloc(sizeof(Node));
    newnode->val = x;
    newnode->next = newnode->random = NULL;
    return newnode;
}

// 在原链表的基础上拷贝节点（即原链表的每个节点后面拷贝一个一样的节点）
void AddNode(Node* head) {
    Node* pcur = head;
    while(pcur) {
        Node* newnode = buyNode(pcur->val);
        Node* next = pcur->next;
        newnode->next = next;
        pcur->next = newnode;
        pcur = next;
    }
}

// 设置新节点的 random，利用关系式 copy(random)->random = pcur(random)->next
void setRandom(Node* head) {
    Node* pcur = head;
    while(pcur) {
        Node* copy = pcur->next;
        if(pcur->random) {
            copy->random = pcur->random->next;
        }
        pcur = copy->next;
    }
}

struct Node* copyRandomList(struct Node* head) {
    if(head == NULL) return head;
    
    // 1. 在原链表基础上拷贝节点并插入到原链表的每个节点之后
    AddNode(head);
    // 2. 设置新节点的 random
    setRandom(head);
    
    // 3. 断开新旧链表
    Node* pcur = head;
    Node* copyHead, *copyTail;
    copyHead = copyTail = pcur->next;
    while(copyTail->next) {
        pcur = copyTail->next;
        copyTail->next = pcur->next;
        copyTail = copyTail->next;
    }
    return copyHead;
}

方法二：C++ Map 映射法（空间复杂度 O(N)）

C++ 中可以使用 std::map 来建立原节点到新节点的映射关系。这样即使 random 指向任意位置，也能通过 map 快速找到对应的拷贝节点。

class Solution {
public:
    Node* copyRandomList(Node* head) {
        std::map<Node*, Node*> nodeMap; // 存储原节点到拷贝节点的映射
        Node* copyhead = nullptr, *copytail = nullptr;
        Node* cur = head;
        
        // 先创建所有新节点并建立映射
        while(cur) {
            if(copytail == nullptr) {
                copyhead = copytail = new Node(cur->val);
            } else {
                copytail->next = new Node(cur->val);
                copytail = copytail->next;
            }
            nodeMap[cur] = copytail;
            cur = cur->next;
        }
        
        // 处理 random 指针
        cur = head;
        Node* copy = copyhead;
        while(cur) {
            if(cur->random == nullptr) {
                copy->random = nullptr;
            } else {
                // 通过 map 获取原节点 random 对应的拷贝节点
                copy->random = nodeMap[cur->random];
            }
            cur = cur->next;
            copy = copy->next;
        }
        return copyhead;
    }
};

以上三种经典数据结构问题的核心思路及代码实现就到这里。实际开发中，根据语言特性和性能要求选择合适的方案即可。