第七期——环形链表2

题目

查看原题目请点击这里~

给定一个链表的头节点  head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

/**

 * Definition for singly-linked list.

 * struct ListNode {

 *     int val;

 *     struct ListNode *next;

 * };

 */

struct ListNode *detectCycle(struct ListNode *head) {

}

思路

在第六期中，我们已经介绍过，可以通过快慢指针来判断链表是否带环结构，具体方法是：

1. 建立两个指针变量，一个是fast指针，另一个是slow指针，让着两个指针变量从链表头开始遍历链表，其中fast指针一次走两步，slow指针一次走一步
2. 如果链表没有环结构，则fast指针最后一定会指向NULL
3. 如果链表存在环状结构，则fast指针就会先进入环结构中，而slow指针会后进入环结构中，fast指针和slow指针在链表的环结构中做追击运动，最后fast指针一定会和slow指针相等

问题1

那么为什么fast指针一次走两步，slow指针一次走一步一定会相遇？它们会错过吗？

答：假设链表带环，两个指针最后都会进环，fast指针先进环，slow指针后进环。当慢指针刚好进环的时候，可能就和fast指针相遇了，最坏的情况就是两个指针之间的距离刚好是环的长度，此时fast指针和slow指针每移动一次，fast指针和slow指针之间的距离就缩小一步，不会出现刚好套圈的情况，因此：fast指针一次走两步，slow指针一次走一步，它们两个一定会相遇的，即相等。

问题2

fast指针一次走3步、4步、......n步行吗？

答：不行。

我们假设slow指针刚好进环的时候，fast指针和slow指针之间的距离为N，环的周长为C

当N为零的时候，fast指针和slow指针恰好相等。

如果fast指针一次走3步，fast指针和slow指针之间的距离一次缩小2步，如果N为偶数，那么fast指针和slow指针的确可以相遇；但是如果N为奇数，fast指针和slow指针会恰好错过，这时fast指针和slow指针之间的新距离为N'=C-1,若C-1为偶数，那么fast指针和slow指针会在第二圈相遇，如果C-1为奇数，那么fast指针和slow指针永远不会相遇。

如果fast指针一次走4步，那么fast指针和slow指针之间的距离一次就缩小3步，N又要分为三种情况讨论，在所有情况中，一定存在fast指针和slow指针不相遇的情况。

当我们已经判断出链表带有环结构，那我们如何能得到进入环的第一个节点呢？

我们设从链表的第一个节点到进入环的第一个节点长度为L，slow指针在环中走的步数为X

fast指针走的距离就是L+n*C+X，slow指针走的距离就是L+X，又因为fast指针走的距离是slow指针走的距离的2倍，所以2*（L+n*C+X）=L+X，最后得到式子：L=（n-1）*C+C-x，于是我们知道，如果我们在相遇点建立一个指针meet，在起始点建立一个指针start，这两个指针分别一次走一步，一定在入口点相遇！

代码1（C语言版）

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode *detectCycle(struct ListNode *head) {
    struct ListNode* slow,*fast;
    slow=fast=head;
    while(fast&&fast->next)
    {
        slow=slow->next;
        fast=fast->next->next;
        if(slow==fast)
        {
            struct ListNode* meet=slow;
            struct ListNode* start=head;
            while(meet!=start)
            {
                meet=meet->next;
                start=start->next;
            }
            return meet;

        }
    }
    return NULL;

}

代码2（C语言版）

我们在第六期介绍了如何找到相交链表的第一个公共节点的方法，所以当我们找到带环链表的相遇点之后，我们也可以把链表的环结构断开，将这个链表分为两个有公共节点的链表，而这个公共节点就是我们要找的入口点

/**
 * 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;
    struct ListNode* tailB=headB;
    int lenA=0;
    int lenB=0;
    while(tailA)
    {
        tailA=tailA->next;
        lenA++;
    }
    while(tailB)
    {
        tailB=tailB->next;
        lenB++;
    }
    if(tailA!=tailB)
        return NULL;
    int gap=abs(lenA-lenB);
    struct ListNode* longlist=headA,*shortlist=headB;
    if(lenA<lenB)
    {
       longlist=headB;
       shortlist=headA;
    }
    while(gap--)
    {
        longlist=longlist->next;
    }
    while(longlist!=shortlist)
    {
        longlist=longlist->next;
        shortlist=shortlist->next;
    }
    return shortlist;
}
struct ListNode *detectCycle(struct ListNode *head) {
    struct ListNode* slow,*fast;
    slow=fast=head;
    while(fast&&fast->next)
    {
        slow=slow->next;
        fast=fast->next->next;
        if(slow==fast)
        {
            struct ListNode* meet=slow;
            struct ListNode* lt1=head;
            struct ListNode* lt2=meet->next;
            meet->next=NULL;
            return getIntersectionNode(lt1,lt2);

        }
    }
    return NULL;

}

持续更新，下期见