环形链表、两个数组中的交集、随机链表的复制

2.3 题目示例

**示例 1：**输入：nums1 = [1,2,2,1], nums2 = [2,2] 输出：[2] **示例 2：**输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4] 输出：[9,4] 解释：[4,9] 也是可通过的

2.4 题目思路

思路 1：一个数组的每个值到另一个数组中遍历，这种方法效率低且容易出错。

思路 2（正确思路）：先将两个数组去重（可用 STL 中的 set），再拿一个数组中的值分别到另一个数组中查找（使用 set::count），最后将遍历找到的插入到一个容器中返回即可。

2.5 解决代码

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.6 对比算法应用

从上面来看这个是没有什么作用的，但是现实生活中不只是用来查找交集的，一般是要找交/差/并集，这时候就有著名的对比算法。

两个数组中找交/差/并集的整体思路：

【示例】使用对比算法找交集:

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());
        // 因为 set 遍历是有序的，有序值，依次比较
        // 小的++，相等的就是交集
        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 题目链接

随机链表的复制

3.2 题目描述

给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random，该指针可以指向链表中的任何节点或空节点。

构造这个链表的深拷贝。深拷贝应该正好由 n 个全新节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点。

返回复制链表的头节点。

用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示：

• val：一个表示 Node.val 的整数。
• random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为 null。

你的代码只接受原链表的头节点 head 作为传入参数。

3.3 题目示例

3.4 题目思路

3.5 解决代码

C 语言解决代码

/** 
 * Definition for a Node.
 * struct Node {
 *     int val;
 *     struct Node *next;
 *     struct Node *random;
 * };
 */
typedef struct Node 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 = 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);
    // 断开新旧链表
    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++ 使用 STL 解决代码

由于出现一个很难处理的问题节点中的 random(随机) 节点怎么拷贝，如果通过节点中的值进行判断指向关系，显然这种方法是不行的。如果想走这种匹配关系，那只能暴力遍历，此时时间复杂度为 O(N^2)。这是因为原链表和拷贝出的链表直接的节点没关系才导致的，C 语言的处理方法是先拷贝在原链表中，这就导致原链表和拷贝出的链表之间的节点有了关系。那 C++ 怎么处理了，C++ 所有 STL 中的 map 由于储存 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;
            }
            // 原节点和拷贝节点 map kv 存储
            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;
    }
};