【算法面试必刷】160. 相交链表

目录

题目

题目链接

思路

复杂度

代码

题目

题目链接

160. 相交链表 – 力扣（LeetCode）https://leetcode.cn/problems/intersection-of-two-linked-lists/description/?envType=study-plan-v2&envId=top-100-liked

思路

利用哈希集合（unordered_set）存储链表 A 的所有节点指针，然后遍历链表 B，第一个出现在集合中的节点即为交点。

复杂度

• 时间复杂度：O(m + n)，其中 m 和 n 分别是链表 A 和 B 的长度。需要遍历两个链表各一次，哈希集合的插入和查找操作平均为 O(1)。

• 空间复杂度：O(m) 或 O(n)，取决于选择存储哪个链表。这里存储了链表 A 的所有节点，因此空间复杂度为 O(m)。

代码

/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
// 创建一个哈希集合，用于存储链表A的所有节点指针
unordered_set<ListNode *> visited;

// 临时指针，用于遍历链表A
ListNode *tmp = headA;
while (tmp != nullptr) {
// 将当前节点指针插入集合
visited.insert(tmp);
// 移动到下一个节点
tmp = tmp->next;
}

// 重新将临时指针指向链表B的头节点
tmp = headB;
while (tmp != nullptr) {
// 检查当前节点是否已经在集合中（即是否在链表A中出现过）
if (visited.count(tmp)) {
// 如果存在，说明这是交点，直接返回该节点
return tmp;
}
// 否则继续遍历下一个节点
tmp = tmp->next;
}

// 遍历完链表B都没有找到交点，则返回nullptr
return nullptr;
}
};