Write a program to find the node at which the intersection of two singly linked lists begins.

For example, the following two linked lists:

A:         a1 → a2                      ↘                       c1 → c2 → c3                   ↗            B:     b1 → b2 → b3

begin to intersect at node c1. 题意：就是求取两个链表的交汇点， 要求：无交汇点返回NULL，否则返回交汇点的地址。

---

暴力思路：O(nm),固定A链表的第一个点，依次遍历B链表看是否有相同的点；接着固定A链表的第二个点，再依次遍历B链表，直到找到相同点为止。 hash解：时间复杂度O(n+m),空间O(n)或者O(m) 两指针解法：我们发现只要两个链表长度一样，就只需同时后移节点指针比较一个，若其中一个较长呢，其实处理一下，把两个链表变成一样长即可。 解法步骤： 1.求出两个链表的长度 2.若一样长，无需处理；若其中一个较长，则只需让较长的链表先走abs(lengthA-lengthB)步即可。 3.同时后移节点指针，直到找到交汇点。 代码：

class Solution {private:    int getLength(ListNode* head){        if(head==NULL) return 0;        ListNode* p=head;        int res=0;        while (p->next!=NULL)        {            ++res;p=p->next;        }        return res;    }public:    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {        if(headA==NULL||headB==NULL) return NULL;        int length_A=getLength(headA);        int length_B=getLength(headB);        ListNode* pA=headA;        ListNode* pB=headB;        int dis=0;        if (length_A>length_B)        {            dis=length_A-length_B;            while (dis>0)            {                --dis;                pA=pA->next;            }        }else if(length_A
     
      0)            {                --dis;                pB=pB->next;            }        }        while (pA!=NULL&&pB!=NULL&&pA!=pB)        {            pA=pA->next;            pB=pB->next;        }        if(pA==pB&&pA!=NULL) return pA;        else return NULL;    }};