剑指OFFER_两个链表的第一个公共节点

剑指OFFER_两个链表的第一个公共节点

题目

输入两个链表,找出它们的第一个公共节点。

如下面的两个链表

剑指OFFER_两个链表的第一个公共节点

在节点 c1 开始相交。

思路

我的思路就是先遍历一个链表,用哈希set保存起来,然后遍历另一个列表,如果遇到已经存过的就返回;

代码

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        unordered_set<ListNode*> ls;
        while (headA) {
            ls.insert(headA);
            headA = headA->next;
        }

        while (headB) {
            if (ls.find(headB) != ls.end()) {
                return headB;
            }
            headB = headB->next;
        }
        return NULL;
    }
};
上一篇:力扣 160 相交链表 快慢指针 双指针


下一篇:微软面试题:剑指 Offer 52. 两个链表的第一个公共节点 出现次数:2