环形链表、数组交集与随机链表复制解析

一、环形链表

1.1 题目描述

给定一个链表的头节点 head，返回链表开始入环的第一个节点。如果链表无环，则返回 null。

为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。注意不允许修改链表。

1.2 解题思路

检测环入口通常有两种主流方法：快慢指针法或哈希集合遍历。

这里我们采用 C++ STL 的 set 容器来遍历链表。核心逻辑很简单：如果链表中的节点不在 set 中就插入；如果在就代表带环，且该节点就是环入口点。需要注意的是，这里存储的是节点的指针而非值，因为节点的值可能有重复，而指针地址是唯一的。

1.3 代码实现

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        std::set<ListNode*> s;
        ListNode* cur = head;
        while(cur) {
            auto it = s.find(cur);
            if(it == s.end()) {
                s.insert(cur);
            } else {
                return *it;
            }
            cur = cur->next;
        }
        return nullptr;
    }
};

二、两个数组中的交集

2.1 题目描述

给定两个数组 nums1 和 nums2，返回它们的交集。输出结果中的每个元素一定是唯一的。我们可以不考虑输出结果的顺序。

2.2 解题思路

暴力遍历虽然可行，但容易受数组大小和重复元素影响。例如示例中若拿 nums2 的值去 nums1 遍历，可能会得到重复结果。

更稳健的思路是先对两个数组去重，再取交集。利用 STL 中的 set 天然有序且去重的特性，可以将一个数组的值依次在另一个数组中查找，找到后存入结果容器即可。

2.3 代码实现

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;
    }
};

2.4 对比算法扩展

在实际工程中，除了找交集，往往还需要处理差集或并集。对于有序集合（如 std::set），可以使用双指针对比算法高效完成。

对比算法逻辑： 由于 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;
    }
};

三、随机链表的复制

3.1 题目描述

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

3.2 解题思路

这个问题难点在于 random 指针的映射关系。原链表和拷贝出的链表之间没有直接关联，如何建立对应关系是关键。

方案一：C 语言插针法（空间复杂度 O(1)） 核心思想是在原链表的基础上拷贝节点，将新节点插入到原节点之后。这样原节点 pcur 和新节点 copy 就有了物理上的相邻关系。设置 random 时，利用 copy->random = pcur->random->next 这一关系式即可。最后断开新旧链表。

方案二：C++ 哈希表法（空间复杂度 O(N)） C++ 中可以利用 map 存储原节点与拷贝节点的映射关系。遍历时先创建所有新节点并存入 map，再次遍历设置 random 指针时，通过 map 查找对应的拷贝节点。

3.3 代码实现

C 语言版本：

/**
 * 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
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;
    
    AddNode(head);
    setRandom(head);
    
    // 断开新旧链表
    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++ 版本：

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 {
                copy->random = nodeMap[cur->random];
            }
            cur = cur->next;
            copy = copy->next;
        }
        return copyhead;
    }
};