环形链表
题目描述
给定一个链表的头节点 head，返回链表开始入环的第一个节点。如果链表无环，则返回 null。
为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。注意不允许修改链表。
思路分析
在之前的讲解中我们讨论过 C 语言的快慢指针解法，虽然经典但实现稍显繁琐。这里我们直接使用 C++ STL 的 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，返回它们的交集。输出结果中的每个元素一定是唯一的。我们可以不考虑输出结果的顺序。
思路分析
暴力遍历两个数组效率较低且容易出错。更优的方案是利用哈希集合去重。
- 去重：先将两个数组分别转换为
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 的链表，每个节点包含一个额外增加的随机指针 random，该指针可以指向链表中的任何节点或空节点。构造这个链表的深拷贝。深拷贝应该正好由 n 个全新节点组成，其中新节点的 next 指针和 random 指针也都应指向复制链表中的新节点。
思路分析
这道题的核心难点在于 random 指针的映射关系。原链表和拷贝链表之间没有天然联系，如何快速找到对应节点是关键。
方案一：C 语言节点穿插法（空间复杂度 O(1)）
不创建新链表结构，而是在原链表每个节点后插入一个拷贝节点。这样原节点 A 的拷贝就在 A->next。通过这种物理连接，A->random->next 就是 A->random 对应节点的拷贝。最后再断开链接恢复原状并提取新链表。
方案二：C++ 映射表法（空间复杂度 O(N)）
利用 std::map<Node*, Node*> 存储原节点到拷贝节点的映射。遍历时先建立所有节点的映射关系，第二次遍历直接通过 map 查找 random 指针的目标。代码逻辑更直观，适合 C++ 环境。
代码实现
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;
}
};