剑指 Offer 52. 两个链表的第一个公共节点

剑指 Offer 52. 两个链表的第一个公共节点
快慢指针

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        if(headA == nullptr || headB == nullptr)  
            return nullptr;
        int lenA=0,lenB=0;
        ListNode *A=headA,*B=headB;
        while(A){    //计算链表A的长度lenA
            A=A->next;
            ++lenA;
        }
        while(B){
            B=B->next;
            ++lenB;
        }
        A=headA,B=headB;
        if(lenA>lenB){
            for(int i=0;inext;
            while(A){                    //A B指针同时前进
                if(A==B) return A;
                A=A->next;
                B=B->next;
            }
        }
        else{
            for(int i=0;inext;
            while(B){
                if(A==B) return A;
                A=A->next;
                B=B->next;
            }
        }
        return nullptr;
    }
};

简洁版写法
逻辑上拼接在对方末尾让路一样长

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        if (headA == nullptr || headB == nullptr) {
            return nullptr;
        }
        ListNode *pA = headA, *pB = headB;
        while (pA != pB) {
            pA = pA == nullptr ? headB : pA->next;    //若A走到尽头则从B头重新开始
            pB = pB == nullptr ? headA : pB->next;
        }
        return pA;
    }
};

哈希表存链表结点

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        unordered_setvisited;
        ListNode* tmp=headA;
        while(tmp){
            visited.insert(tmp);
            tmp=tmp->next;
        }
        tmp=headB;
        while(tmp){
            if(visited.count(tmp)) return tmp;
            tmp=tmp->next;
        }
        return nullptr;
    }
};