一 环形链表
1.1 题目链接：环形链表 II
1.2 题目描述：
给定一个链表的头节点 head，返回链表开始入环的第一个节点。如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。注意不允许修改链表。
1.3 题目示例：
1.4 题目思路：
在之前的讲解中介绍过 C 语言的快慢指针方法，C 语言相对复杂，这里我们使用 C++ STL 实现。利用 STL 的 set 遍历链表，如果链表中的节点不在 set 中就插入（注意这里不是插入节点的值，而是节点的指针，因为节点的值可能有几个相等）；如果在就代表带环，并且该节点就是环入口点。
1.5 解决代码
// 1 cur 不在 set 对象中，就插入到 set 对象中
// 2 cur 在 set 对象中就带环，并且该节点就是环入口点
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
std::set<ListNode*> s;
ListNode* cur = head;
while(cur) {
auto it = s.find(cur); // 查找 cur 是否在 set 对象中
if(it == s.end()) { // cur 不在 set 对象中，就插入到 set 对象中
s.insert(cur);
} else { // cur 在 set 对象中就带环，并且该节点就是环入口点
return *it;
}
cur = cur->next;
}
return nullptr;
}
};
二 两个数组中的交集
2.1 题目链接：两个数组的交集
2.2 题目描述：
给定两个数组 nums1 和 nums2，返回它们的交集。输出结果中的每个元素一定是唯一的。我们可以不考虑输出结果的顺序。
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 如果拿 nums1 中的每个值到 nums2 中遍历可行，但是如果拿 nums2 中的值到 nums1 中就会得到结果 [9,4,9,4] 是不正确的，所以这种方法不行。
思路 2（正确思路）：先将两个数组去重（要先排序只有排序了才能真正的去重），去重可用 STL 中的 set，也可以用算法库中的去重算法 std::unique。再拿一个数组中的值分别到另一个数组中找（使用 STL->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;
}
};
【对比算法在生活中的应用】
例如我们要更换手机，而之前的手机中有许多的照片是要的，此时怎么办呢？这时候可以将云端照片和本地照片进行对比，判断是否要导入到云端，而照片存在，但是照片可能存在更改，这时候可以比较照片最后的时间。所以这个对比算法在生活中还是有很多用处的。
三 随机链表的复制 (两种解决办法 C 语言 [了解思路]、C++)
3.1 题目链接：随机链表的复制
3.2 题目描述：
给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random，该指针可以指向链表中的任何节点或空节点。
构造这个链表的深拷贝。深拷贝应该正好由 n 个全新节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点。
例如，如果原链表中有 X 和 Y 两个节点，其中 X.random --> Y。那么在复制链表中对应的两个节点 x 和 y，同样有 x.random --> y。
返回复制链表的头节点。
用一个由 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 解决代码】
上面讲了 C 语言的处理方法，由于出现一个很难处理的问题节点中的 random(随机) 节点怎么拷贝，如果通过节点中的值进行判断指向关系（如果一个节点的 random 指向的节点值是 1，而节点值为 1 的节点不止一个有怎么解决呢？显然这种方法是不行的），如果想走这种匹配关系，那只能暴力遍历，此时时间复杂度为 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) // 如果原节点的 random 为空则拷贝节点的 random 也为空
{
copy->random = nullptr;
} else { // 如果原节点的 random 不为空则，则使用 map[]，传入参数原链表节点指针，得到拷贝出的对应节点
copy->random = nodeMap[cur->random];
}
cur = cur->next;
copy = copy->next;
}
return copyhead;
}
};
