【算法面试必刷】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; } };