相交链表（力扣160）

题目如下：

这道题首先要判断有没有环，没环返回NULL，有环返回第一个相交节点。

以下是题目给的一些传参和结构体定义。

传参是链表A和B的头结点。

判断有没有环，只需要判断链表A和B的尾节点是不是同一个

    struct ListNode*nodeA=headA;
    struct ListNode*nodeB=headB;
    //int lenA=0;
    //int lenB=0;
    while(nodeA->next){
        nodeA=nodeA->next;//得到链表A的尾节点
        //++lenA;
    }
    while(nodeB->next){
       nodeB=nodeB->next;//得到链表A的尾节点
       //++lenB;
    }
    if(nodeA!=nodeB){//判断是否相等
        return NULL;//不相等就返回空
    }

如果有环，我们就开始找第一个相交的节点

我们的思路是这样滴

如上图所示，搞两个指针。第一个指针从a1开走，第二个指针从b2开走。两个指针同时出发，直到两个指针相等为止，就找到了第一个相交节点c1

关键点就在于如何找到B链表的b2结点，意思就是说，这两个链表的长度不一样，怎么让它们 从长度相同的地方开始走。。

总的思路是，得到长链表与短链表长度的差值L（长链表比短链表多了多少个节点），然后让长链表向前走L个节点，停下。此时长链表与短链表的长度就一样了，让它们同时走，直到相遇，走到第一个节点

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    struct ListNode*nodeA=headA;
    struct ListNode*nodeB=headB;
    int lenA=0;
    int lenB=0;
    while(nodeA->next){
        nodeA=nodeA->next;
        ++lenA;//记录链表A的长度
    }
    while(nodeB->next){
       nodeB=nodeB->next;
       ++lenB;//记录链表B的长度
    }
    if(nodeA!=nodeB){
        return NULL;
    }
    int gap=abs(lenA-lenB);//abs是绝对值的意思，记录链表A和B的相对长度
    struct ListNode*longList=headA;//假设链表A比较长，而B比较短
    struct ListNode*shortList=headB;
    if(lenB>lenA){//如果B比A长，就让B为长链表，A为短链表
        longList=headB;
        shortList=headA;
    }

    while(gap--){
        longList=longList->next;//让长链表走到与短链表头结点一样长的地方
    }

    while(longList!=shortList)//找第一个相交的节点
    {
        longList=longList->next;
        shortList=shortList->next;
    }
//找到了就返回第一个相交的节点
    return longList;//也可以写成return shortList
}