相交链表
题目描述
思路
方法一：哈希表
遍历链表headA，将链表headA中的每个节点加入哈希表中。然后遍历链表headB，对于遍历到的每个节点，判断该节点是否在哈希表中： 如果当前节点不在哈希表中，则继续遍历下一个节点； 如果当前节点在哈希表中，则后面的节点都在哈希表中，即从当前节点开始的所有节点都在两个链表的相交部分，因此在链表headB中遍历到的第一个在哈希表中的节点就是两个链表相交的节点，返回该节点。
这个做法的时间复杂度是$O(m+n)$，其中$m$和$n$分别是两个链表的长度。需要遍历两个链表各一次，并对哈希表进行一次遍历。空间复杂度是$O(m)$，因为需要将链表headA中的所有节点存储在哈希表中。
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
unordered_set <ListNode *> visited;
ListNode* temp = headA;
while (temp != nullptr) {
visited.insert(temp);
temp = temp->next;
}
temp = headB;
while (temp != nullptr) {
if (visited.count(temp)) {
return temp;
}
temp = temp->next;
}
return nullptr;
}
};
方法二：用双指针对空间复杂度进行优化
时间复杂度已经没有优化的空间了，因为不管怎么优化，都需要遍历两个链表。但是空间复杂度还可以优化到$O(1)$。可以使用双指针的方法来解决。
这里可以通过图解来证明这个方法的正确性：
直观地看，对于两个指针，依次遍历两个链表的每个节点。无论两个链表是否相交，两个指针最后都会遍历完所有节点。如果两个指针最后指向同一个节点，则两个链表相交；如果两个指针最后指向空节点，则两个链表没有相交，返回null。
这个想法的具体流程如下（来自力扣官方题解）：
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
ListNode* p1 = headA;
ListNode* p2 = headB;
if (headA == nullptr || headB == nullptr) {
return nullptr;
}
while(p1 != p2) {
// 学习一下这里的用法，能够简化if-else结构
p1 = p1 == nullptr ? headB : p1->next;
p2 = p2 == nullptr ? headA : p2->next;
}
return p1;
}
};
C++中的map与set
参考链接：https://zhuanlan.zhihu.com/p/523850774
map（字典）
map的官网解释是：
Map 对象保存键值对，并且能够记住键的原始插入顺序。任何值（对象或者原始值）都可以作为一个键或一个值。
map的特点： - 键值对 - 能够记住插入顺序 - 键和值可以是任何类型
map的使用方法在上一篇博客中已经有介绍，这里略过了。
set（集合）
set的官网解释是：
Set 对象允许你存储任何类型的唯一值，无论是原始值或者是对象引用。
set的特点： - 唯一值 - 键和值可以是任何类型
set的“唯一值”说明set存储的数据是不会重复的。除此之外，Set 也是一个对象，但是它是一个类数组对象，也就是说它长得像数组，我们通常直接称它为 Set 对象。
set的基本使用
在使用set时，需要引入头文件：
#include <set>
// 声明一个set对象s
set<int> s;
// 声名一个无序的set对象u_s
unordered_set<int> u_s;
// 插入元素
s.insert(1);
// 删除元素
s.erase(1);
// 查找元素
s.find(1);
// 计算size
s.size();
一些常用的成员方法：
c++ stl容器set成员函数:
| 方法 | 描述 |
|---|---|
| begin() | 返回指向第一个元素的迭代器 |
| clear() | 清除所有元素 |
| count() | 返回某个值元素的个数 |
| empty() | 如果集合为空，返回true |
| end() | 返回指向最后一个元素的迭代器 |
| equal_range() | 返回集合中与给定值相等的上下限的两个迭代器 |
| erase() | 删除集合中的元素 |
| find() | 返回一个指向被查找到元素的迭代器 |
| get_allocator() | 返回集合的分配器 |
| insert() | 在集合中插入元素 |
| lower_bound() | 返回指向大于（或等于）某值的第一个元素的迭代器 |
| key_comp() | 返回一个用于元素间值比较的函数 |
| max_size() | 返回集合能容纳的元素的最大限值 |
| rbegin() | 返回指向集合中最后一个元素的反向迭代器 |
| rend() | 返回指向集合中第一个元素的反向迭代器 |
| size() | 集合中元素的数目 |
| swap() | 交换两个集合变量 |
| upper_bound() | 返回大于某个值元素的迭代器 |
| value_comp() | 返回一个用于比较元素间的值的函数 |
文档信息
- 本文作者：焦逸凡
- 本文链接：https://ailovejinx.github.io/wiki/leetcode160/
- 版权声明：自由转载-非商用-非衍生-保持署名（创意共享3.0许可证）