1. Intersection of Two Linked Lists My Submissions QuestionEditorial Solution
   
   Total Accepted: 72580 Total Submissions: 239762 Difficulty: Easy
   
   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.

思路：两条链表如果相交，那从交点开始，后面一定都是相等的

那如何求第一个交点呢？

时间复杂度：O(n)

要么返回空

有交点时，说明尾部是对齐的，要找到第一个交点，只要让长的链表先走len1-len2步，这里假设len1是那条长链，那么此时再同时走，相遇的第一个节点便是交点

/**

 * Definition for singly-linked list.

 * struct ListNode {

 *     int val;

 *     ListNode *next;

 *     ListNode(int x) : val(x), next(NULL) {}

 * };

 */

class Solution {

public:

    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {

        if(headA==NULL||headB==NULL)return NULL;//有一为空返回

        if(headA==headB)return headA;//头部相同返回

        ListNode *l1=headA,*l2=headB;

        int len1=1,len2=1;

        while(l1->next){//遍历记录长度

            l1=l1->next;

            len1++;

        }

        while(l2->next){

            l2=l2->next;

            len2++;

        }

        ListNode *p = len1>len2?headA:headB;    //p为长链表

        ListNode *psmall=len1>len2?headB:headA;    //psmall为短链表

        int count=abs(len2-len1);

        while(count--){

                p=p->next;

        }

        while(p!=NULL&&psmall!=p){

            p=p->next;

            psmall = psmall->next;

        }

        if(p!=NULL)return p;          //有交点

        else return NULL;             //无交点

    }

};