环形链表检测
题目描述
给定一个链表的头节点 head，返回链表开始入环的第一个节点。如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。注意不允许修改 链表。
解题思路
关于快慢指针的经典解法，之前有过详细探讨，这里我们直接用 C++ STL 来简化实现。核心逻辑是利用哈希集合 set 遍历链表：
- 如果当前节点不在
set中，就插入该节点的指针（注意是节点地址而非值，因为节点值可能重复）。 - 如果当前节点已经在
set中，说明遇到了重复访问的节点，即发现环，且该节点就是环的入口点。
代码实现
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，返回它们的 交集。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序。
解题思路
暴力遍历虽然可行，但容易受数组选择影响导致结果错误。更稳健的思路是先对两个数组去重，再查找共同元素。
利用 STL 中的 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;
for(auto e : s1) {
if(s2.count(e)) {
v.push_back(e);
}
}
return v;
}
};
扩展：对比算法优化
由于 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 指针的映射关系。如果仅通过节点值判断，无法区分相同值的节点。
方法一：C 语言实现（节点穿插法）
这种方法不需要额外的哈希表空间，直接在原链表上操作：
- 拷贝节点：在每个原节点后插入一个新节点。
- 设置 random：利用
copy->random = pcur->random->next的关系式。 - 拆分链表：将新旧链表分离。
/**
* 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++ STL 实现（哈希映射法）
C++ 中可以使用 map 巧妙地将原链表节点和拷贝节点联系起来。map<Node*, Node*> 存储了原节点到拷贝节点的映射关系，这样在设置 random 指针时，可以直接通过原节点找到对应的拷贝节点。
class Solution {
public:
Node* copyRandomList(Node* head) {
std::map<Node*, Node*> nodeMap;
Node* copyhead = nullptr, *copytail = nullptr;
Node* cur = head;
// 1. 创建新节点并建立映射
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;
}
// 2. 处理 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;
}
};
