[数据结构与算法]剑指offer 52.两个链表的第一个公共结点

题目描述：

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

考察点：

本题主要考察在链表题中，对哈希集合 unordered_set的使用，或者双指针的灵活运用。

解题思路：

这个链表题主要有两种解题思路：

1、使用哈希集合

使用哈希集合来存储遍历到的第一次出现的结点，
可以先遍历A链表，将A链表中所有的结点都存放到哈希集合中
然后再遍历B链表，如果出现当前结点已经在哈希集合中，那么这个点就是第一个交点，返回这个结点
如果将B链表都遍历完还没有发现有重复结点在哈希集合中，就返回NULL。

2、使用双指针

所谓的双指针，就是A链表的头节点处定义一个A指针，B链表的头节点处定义一个B指针，然后通过遍历消除长度差的方式来寻找相交结点。

双指针的两种思路（总而言之都是为了消除长度差）：

2.1通过长度差改变较长链表头节点位置

定义两个长度变量lena,lenb,分别记录链表的长度
然后让较长链表的头节点往后移动，以达到消除长度差的目的
如图：

lenb-lena=1,长度差为1，所以较长链表的头节点headB向后移动1位
移动之后：
消除长度差之后，两个链表的头节点再分别往后遍历，遇到交点就返回，
否则返回NULL

2.2“相遇”法

如图：

pa将A链表走完之后再去走B链表，
同理pb将B链表走完再去走A链表
pa和pb分别转换到对方的链表之后，如果遇到相同的结点，就一定是第一个相交的结点，此时返回这个相交的结点，
如果交换之后还没有遇到相同的结点，就返回NULL

代码(C++)：

1：

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        if(headA==NULL||headB==NULL)
        {
            return NULL;
        }
        unordered_set<ListNode *>visit;//unorderd基于哈希表
        ListNode* tmp=headA;
        while(tmp!=NULL)
        {
            visit.insert(tmp);
            tmp=tmp->next;
        }
        tmp=headB;
        while(tmp!=NULL)
        {
            if(visit.count(tmp))//这个结点出现次数不为0
            {
                return tmp;
            }
            tmp=tmp->next;
        }
        return NULL;

    }
};

2.1：

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) 
    {
        if(headA==NULL||headB==NULL)
        {
            return NULL;
        }
        ListNode *pa=headA;
        ListNode *pb=headB;
        int lena=0;
        int lenb=0;
        while(pa!=NULL)
        {
            lena++;
            pa=pa->next;
        }
        while(pb!=NULL)
        {
            lenb++;
            pb=pb->next;
        }
        if(lena<lenb)
        {
            int n=lenb-lena;
            while(n--)
            {
                headB=headB->next;
            }
        }
        else
        {
            int n=lena-lenb;
            while(n--)
            {
                headA=headA->next;
            }
        }
        pa=headA;
        pb=headB;
        while(pa!=pb)
        {
            pa=pa->next;
            pb=pb->next;
        }
        return pa;
    }
};

2.2:

class Solution {
public:
   ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
   assert(headA!=NULL&&headB!=NULL);
   struct ListNode* pa=headA;
   struct ListNode* pb=headB;
   while(pa!=pb)
   {
       if(pa==NULL)
       {
           pa=headB;
       }
       else
       {
           pa=pa->next;
       }
       if(pb==NULL)
       {
           pb=headA;
       }
       else
       {
           pb=pb->next;
       }
       
   } 
       return pa;
   }
};