剑指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;
    }
};