LeetCode 160.相交链表

题目：

思路：

1.可以看出这是两个链表尾部a2和b3的next连接到了同一个地址c1，形成交点。

2.那么我们可以先在两个链表分别定义一个指针tailA,tailB，从头开始遍历到尾，通过判断他们遍历后的尾部地址是否相同来看有没有相交。

3.并且从头开始遍历时定义一个记录步数的变量lenA,lenB，之后有用处。

4.确定相交后，我们再分别定义一个指针shortList,longList，也是从头开始走，并且通过之前记录步数的变量来确定哪一个链表更长，让更长的链表先走lenA-lenB的绝对值步，使长链表和短链表在同一起点，这时它们开始遍历，当长链表与短链表地址相等时，就是交点位置了

PS:任意需要返回的函数都需要语法逻辑（返回值），他不能检测执行逻辑，所以在非void函数中我们都需要在结尾返回一个值

代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    struct ListNode* tailA = headA, *tailB = headB;
    int lenA = 1; //可以为0，就算为1他们也是走同样的路程，不过为1可以更精确的求路程
    int lenB = 1;
    while(tailA->next) //A和B链表遍历，并统计走的路程
    {
        tailA = tailA->next;
        ++lenA;
    }
    while(tailB->next)
    {
        tailB = tailB->next;
        ++lenB;
    }
    if(tailA != tailB) //尾节点地址相同就是相交
    {
        return NULL;
    }
    //相交，求交点，长的差距步，在同时走找交点
    struct ListNode* shortList = headA,*longList = headB; //定义一个长和短接收头
    if(lenA > lenB) //判断是谁长谁短
    {
        longList = headA;
        shortList = headB;
    }
    int gap = abs(lenA - lenB); //abs求绝对值
    while(gap--)
    {
        longList = longList->next; //让长的先走gap步
    }
    while(shortList && longList)
    {
        if(shortList == longList) //已经到达交点位置
        return shortList; //long和short都可以
        shortList = shortList->next; //没有到达就继续往后走
        longList = longList->next;
    }
    return NULL;
}