[数据结构与算法]链表相关算法题（找出两个链表相交的第一个结点，判断链表是否带环，返回链表入环的第一个结点）

一、相交链表

1、题目要求

2、解题方法

?

相交的情况有三种：

首先判断两个链表是否相交，判断方法为找到两个链表的最后一个结点，比较它们是否相等（注意这里比较的是地址），相等的话它们就一定相交。

然后找它们相交的起始结点，方法为定义两个指针，先让两个指针移动到距离相交的起始节点相等的位置，然后让两个指针同时向后移动，直到它们相等（地址相等）。

3、代码

typedef struct ListNode Node;
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    //有一个链表为空时
    if(headA == NULL || headB == NULL){
        return NULL;
    }
    int size1 = 1;
    int size2 = 1;
    Node* tail1 = headA;
    Node* tail2 = headB;
    Node* cur1 = headA;
    Node* cur2 = headB;
    //找到链表的尾结点
    while(tail1){
        tail1 = tail1->next;
        size1++;
    }
    while(tail2){
        tail2 = tail2->next;
        size2++;
    }
    //尾结点不同时，两个链表不相交
    if(tail1 != tail2){
        return NULL;
    }
    //两个链表相交，让两个指针移动到离交点等距离时
    if(size1 > size2){
        while(size1 != size2){
            cur1 = cur1->next;
            size1--;
        }
    }else{
        while(size1 != size2){
            cur2 = cur2->next;
            size1++;
        }
    }
    //让两个指针同时移动，相等时就是它们的交点
    while(cur1 != cur2){
        cur1 = cur1->next;
        cur2 = cur2->next;
    }
    return cur1;
}

二、判断链表是否有环

1、题目要求

?

?2、解题方法

使用快慢指针，fast指针每次走两步，slow指针每次走一步，fast指针先进环，slow指针后进环，相对于slow指针来说，fast指针其实是一个结点一个结点的靠近slow的，所以如果成环的话它们一定相交。

3、代码

typedef struct ListNode Node;
bool hasCycle(struct ListNode *head) {
    //使用快慢指针
    //这是因为fast是走两步，slow是走一步，其实相对于slow来说，
    //fast是一个节点一个节点的靠近slow的，所以fast一定可以和slow重合。
    Node* fast = head;
    Node* slow = head;
    //注意循环条件
    while(fast != NULL && fast->next != NULL){
        slow = slow->next;
        fast = fast->next->next;
        if(fast == slow){
           return true; 
        }
    }
    return false;
}

?三、找链表入环的第一个结点

1、题目要求

?

2、解题思路

方法一：可以用快慢指针先判断链表是否成环，然后根据快慢指针相交的结点把原链表断开，这样就把它转化成了第一个问题。和第一题差不多，就不写代码了。

方法二：让一个指针从链表起始位置开始遍历链表，同时让一个指针从判环时相遇点的位置开始绕环运行， 两个指针都是每次均走一步，最终肯定会在入口点的位置相遇。

证明：

3、代码

?

typedef struct ListNode Node;
struct ListNode *detectCycle(struct ListNode *head) {
    //先使用快慢指针判断链表是否成环
    Node* slow = head;
    Node* fast = head;
    while(fast && fast->next){
        fast = fast->next->next;
        slow = slow->next;
        if(fast == slow){
            break;
        }
    }
    //不成环直接返回NULL
    if(fast == NULL || fast->next == NULL){
        return NULL;
    }
    Node* cur = head;
    //一个指针从判环相遇点移动，一个指针从起始点开始移动，
    //相遇的时候就是入环的第一个结点
    while(cur != slow){
        cur = cur->next;
        slow = slow->next;
    }
    return cur;
}