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

题目描述：

 这里的1不是公共节点，只是链表的val一样

使用C++STL：unordered_map

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        unordered_mapmap;
        ListNode* temp=headA;
        while(temp!=NULL)
        {
            map[temp]=true;
            temp=temp->next;
        }
        temp=headB;
        while(temp!=NULL)
        {
            if(map[temp]==true)
            return temp;

            temp=temp->next;
        }
        return NULL;
    }
};

算出两个链表相差的长度n，然后长的链表的指针先走n步

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode* tempA;
        ListNode* tempB;
        
        int lengthA=0,lengthB=0;

        if(headA==NULL || headB==NULL)
        return NULL;
        tempA=headA;
        while(tempA!=NULL)
        {
            lengthA++;
            tempA=tempA->next;
        }
        tempB=headB;
        while(tempB!=NULL)
        {
            lengthB++;
            tempB=tempB->next;
        }

        if(lengthA>lengthB)
        {
            tempA=headA;
            for(int i=0;inext;

            tempB=headB;
            while(tempA!=NULL)
            {
                if(tempA==tempB)
                return tempA;
                tempA=tempA->next;
                tempB=tempB->next;
            }

        }
        else
        {
            tempB=headB;
            for(int i=0;inext;
            tempA=headA;
            while(tempB!=NULL)
            {
                if(tempA==tempB)
                return tempA;
                tempA=tempA->next;
                tempB=tempB->next;
            }

        }
        return NULL;

    }
};

两个链表长度分别为L1+C,L2+C。C是公共链表的长度，第一个指针走了L1+C步之后，到第二个链表再走L2步。第二个指针走了L2+C步之后，到第一个链表再走L1步。这样两个指针都走L1+L2+C步，就会相遇，如果两个指针没有公共部分的话 都会走到NULL，然后相等，返回NULL。

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {

        ListNode* tempA=headA;
        ListNode* tempB=headB;

        if(tempA==NULL || tempB==NULL)
        return NULL;

        while(tempA!=tempB)
        {
            tempA= tempA==NULL? headB:tempA->next;
            tempB= tempB==NULL? headA:tempB->next;
        }
        return tempA;


    }
};