剑指offer 23. 链表中环的入口

1.问题描述

给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。

2.解决思路

2.1 思路1

1）先判断链表是否有环；

2）如果有环，假设环里面有n个结点，除去环之外有m个结点，使用快慢指针fast和slow，开始都指向头结点head，每次移动一个结点：

设fast指针先走x了步，我们希望slow指针从1结点经过m步到达第m+1个结点（即环入口）的时候，fast指针也正好到达了环入口，所以有如下关系：

总的结点数：n + m

到达环入口时，slow经过m+1个结点, fast 经过了n+m+1

(1+x) + m = n + m + 1——> x = n，即fast指针要先走n步。

所以需要做的关键事情：链表有环的情况下，统计链表里面的结点个数。

总结解决思路：

a）判断链表是否有环：快慢指针是否会相遇，相遇了，记下相遇点A。

b）从相遇点A开始，移动指针到再次回到A，以统计环中结点的个数n。

c）fast指针和slow指针指向head，fast先走n步，相遇时即为环入口。

2.2 思路2

如上图所示，假设相遇时候快指针fast（每次走2步）走了m圈环，慢指针（每次走1步）走了n圈环，相遇点在B，则有如下关系：

fast的路程：Sf = X + m * C + Y

slow的路程：Ss=X + n * C + Y

Sf = 2 * Ss ——> 2( X + n * C + Y) = X + m * C + Y——> X = (m - 2n) * C - Y = (m - 2n - 1) * C + (C-Y) = (m - 2n - 1) * C + Z

即环前面的路程 = 环的长度的整数倍（可能为0） + Z

所以总结思路2为：

1）先判断是否存在环；
2）有环：让一个指针从起点A开始走，让一个指针从相遇点B开始继续往后走，2个指针速度一样，那么，当从原点的指针走到环入口点的时候（此时刚好走了x），从相遇点开始走的那个指针也一定刚好到达环入口点。所以两者会相遇，且恰好相遇在环的入口点。

3.代码实现

3.1 思路1

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/
class Solution {
public:
    ListNode* EntryNodeOfLoop(ListNode* head){
        if(head==NULL || head->next == NULL)
            return NULL;
        //判断是否有环
        ListNode* slow = head->next;
        ListNode* fast = head->next->next;
        ListNode* MeetNode = NULL;
        while(fast != NULL && slow != NULL){
            if(slow == fast) {
                MeetNode = slow;
                break;
            }
            slow = slow->next;
            fast = fast->next;
            if(fast != NULL)
                fast = fast->next;
        }
        //统计环中结点的个数
        if(MeetNode == NULL) return NULL;
        int NumOfLoop = 1;
        while(fast->next != MeetNode){
            ++NumOfLoop;
            fast = fast->next;
        }
        //寻找环的入口
        fast = head;
        slow = head;
        for(int i = 0; i<NumOfLoop; ++i)
            fast = fast->next;
        while(slow != fast){
            fast = fast->next;
            slow = slow->next;
        }
        return slow;
                   
    }

};

3.2 思路2

class Solution {
public:
    ListNode* EntryNodeOfLoop(ListNode* head){
        if(head==NULL || head->next == NULL)
            return NULL;
        //判断是否有环
        ListNode* slow = head->next;
        ListNode* fast = head->next->next;
        ListNode* MeetNode = NULL;
        while(fast != NULL && slow != NULL){
            if(slow == fast) {
                MeetNode = slow;
                break;
            }
            slow = slow->next;
            fast = fast->next;
            if(fast != NULL)
                fast = fast->next;
        }
        //使用快慢指针
        if(MeetNode == NULL) return NULL;
        fast = head;
        while(fast != MeetNode){
            fast = fast->next;
            MeetNode = MeetNode->next;
        }
        return MeetNode;
    }
};