环形链表、两个数组交集与随机链表复制详解

对比算法补充

如果是有序数组，或者需要频繁进行集合运算，可以使用双指针对比。因为 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();
        
        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++ 推荐）

利用 std::map<Node*, Node*> 建立原节点到新节点的映射关系。第一遍遍历创建所有新节点并存入 Map；第二遍遍历设置 next 和 random 指针时，直接查表即可。 这种方法逻辑清晰，代码简洁，时间复杂度 O(N)，空间复杂度 O(N)。

方案二：原地插值（C 语言常见思路）

在原链表每个节点后插入一个新节点，形成 A -> A' -> B -> B' 的结构。这样 A' 的 random 就可以通过 A.random->next 直接获取。最后再拆分链表。 这种方法空间复杂度优化到了 O(1)，但会修改原链表结构，且代码相对复杂，调试难度大。

下面主要展示基于哈希表的通用解法，这也是面试中最稳妥的实现方式。

代码实现

class Solution {
public:
    Node* copyRandomList(Node* head) {
        std::map<Node*, Node*> nodeMap; // 存储原节点到拷贝节点的映射
        Node* copyhead = nullptr;
        Node* 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;
    }
};

在实际开发中，遇到类似的数据同步或状态迁移问题，这种'建立映射'的思路非常通用。比如旧手机照片导入新手机云盘，就需要比对文件 ID 或时间戳来确认是否已存在，避免重复上传。