160. Intersection of Two Linked Lists

第一想法是建一个unordered_set，时间复杂度O（m+n），空间复杂度O(m)或O(n)

更巧妙的方法是用两个指针，分别指向两个list。当遍历结束时，指向另一个list的head。两个指针的相遇点就是intersection开始的地方。空间复杂度O(1）。

 

unordered_set

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        unordered_set<ListNode *> s;
        ListNode *p;
        p = headA;
        while (p){
            s.insert(p);
            p = p->next;
        }
        p = headB;
        while (p){
            if (s.count(p))
                return p;
            p = p->next;
        }
        return NULL;
    }
};

 

Two Pointers

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode *p1=headA, *p2=headB;
        while (p1!=p2){
            p1 = p1 ? p1->next : headB;
            p2 = p2 ? p2->next : headA;
        }
        return p1;
    }
};