链表三题：环检测、数组交集与随机链表复制

环形链表

题目描述

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

为了表示链表中的环，评测系统内部用整数 pos 标记尾节点连接到的位置（索引从 0 开始）。如果 pos 是 -1，表示没有环。pos 只用于描述数据，不会作为参数传进来。题目也明确要求不能修改链表。

思路分析

前面如果已经写过快慢指针，这里我更倾向于直接用 set。原因很简单：思路直，不容易在环入口判断上绕晕，代码也短。

遍历链表时，把访问过的节点指针放进集合里。当前节点如果已经在集合中，说明第一次重复遇到的就是环入口；如果一路走到 nullptr 都没重复，那就说明链表无环。

这里存的是节点指针，不是节点值。这个区别不能省，值重复很常见，地址才是真正的唯一标识。

代码实现

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

两个数组中的交集

题目描述

给定两个数组 nums1 和 nums2，返回它们的交集。结果中的每个元素只能出现一次，顺序不做要求。

思路分析

这题直接暴力扫，能过但不漂亮，数据一大就显得笨。更顺手的做法是先去重，再找交集。

我这里保留两种写法。第一种更直接：把两个数组转成 std::set，顺便完成去重，然后遍历其中一个集合，在另一个集合里查找。第二种是利用 set 天然有序的性质，改成双指针同步推进。后者思路更像'两个有序数组求交集'，在数据量稍大时通常也更省事。

代码实现

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        // 利用 set 自动去重
        std::set<int> s1(nums1.begin(), nums1.end());
        std::set<int> s2(nums2.begin(), nums2.end());
        vector<int> v;
        
        // 遍历 s1，在 s2 中查找
        for(auto e : s1) {
            if(s2.count(e)) {
                v.push_back(e);
            }
        }
        return v;
    }
};

双指针写法：

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 的链表，每个节点除了 next 之外还有一个额外的随机指针 random，它可以指向链表中的任意节点，也可以指向空。要求构造这个链表的深拷贝。新链表必须由 n 个全新节点组成，而且这些节点的 next 和 random 都要指向新链表内部对应的节点。

思路分析

这题真正麻烦的地方，不是复制 next，而是处理 random 的对应关系。原链表和新链表之间没有现成的映射，想把'原节点指向谁'同步到'复制节点指向谁'，必须先建立一层关系。

C 语言节点穿插法

这是空间复杂度 O(1) 的做法，但过程不算优雅。做法是把复制节点直接插到原节点后面，这样原节点 A 的复制节点就是 A->next。一旦这个结构建立起来，A->random->next 就能找到 A->random 对应的复制节点。最后再把链表拆开，原链表恢复原样，新链表也被单独取出来。

C++ 映射表法

如果是在 C++ 里写，我一般会直接用 std::map<Node*, Node*>。先遍历一遍建立'原节点 -> 复制节点'的映射，再遍历一次补齐 random。逻辑更直，也更不容易在断链和恢复链表时出错。代价就是多用一份空间。

代码实现

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