相交链表 + 确定环形链表 + 查找环形链表的入口节点 - I. 相交链表

相交链表

相交：两个链表从头开始遍历，尾节点一定是同一个节点。

情况一：当两个链表长度相同时：

情况二：当两个链表长度不同时：

思路：

1. 求两个链表长度的差值gap。
2. 让长链表先走gap个节点。
3. 分别遍历两个链表，比较是否为同一个节点，若是则相交，否则不相交。

代码如下：

typedef struct ListNode ListNode;

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) 
{
    ListNode* la = headA;
    ListNode* lb = headB;
    int lengthA = 0, lengthB = 0;
    while(la)
    {
        lengthA++;//求链表A的长度
        la = la->next;
    }
    while(lb)
    {
        lengthB++;//求链表B的长度
        lb = lb->next;
    }
    //求链表A与链表B长度差的绝对值
    int gap = abs(lengthA - lengthB);

    //找出长链表与短链表
    ListNode* longList = headA;
    ListNode* shortList = headB;
    if(lengthB > lengthA)
    {
        longList = headB;
        shortList = headA;
    }

    //让长链表先走gap个节点
    while(gap--)
    {
        longList = longList->next;
    }

    //此时longList与shortList指针在相对的位置上（同时遍历链表为NULL）
    //判断两个链表是否相交
    while(longList && shortList)
    {
        if(longList == shortList)
        {
            //链表相交
            return longList;
        }
        //两个指针继续往后走
        longList = longList->next;
        shortList = shortList->next;
    }
    //链表不相交
    return NULL;
}