一道编程题——寻找环的入口节点

题目描述与分析

对于一个给定的链表，返回环的入口节点，如果没有环，返回null，给出不利用额外空间的解法

这一题是之前判断链表是否有环的进阶版本，不仅要判断存不存在环，还要找出环的入口节点。

如上图，环的两种形式，则分别返回节点3和节点1.

借助之前的判断是否存在环的函数（用快慢指针实现），我们可以得知是否存在环，以及存在环的情况下，快慢指针的相遇节点。寻找到环的入口节点需要借助这个相遇节点。

如上图，X为链表头节点，Y为环的入口，Z为相遇节点。a,b,c分别为沿着链表方向，X与Y，Y与Z，Z与Y之间的节点数。

由于快慢指针相遇到Z点，可知慢指针行进距离为 $a+b$，又由于快指针的速度是慢指针的2倍，所以快指针的行进距离为 $2*(a+b)$。 并且由于快指针最终也停在了Z点（假设绕环n次），则可知 $2*(a+b)= a + b + k*n$ ，即 $a+b = k*n$ 。

现在我们已经获得了两个节点X，Z的位置了，从这两个节点到入口节点Y的路程分别为 a 和 $k*n -b$ ，并且a = $k*n - b$。

所以，可以通过设置一个指针从X开始，另外一个指针从Z，同时以相同的速度前进，当他们相遇时，正好在入口节点上。

代码实现

python实现

class Solution:
    def detectCycle(self , head ):
        # write code here
        if not head or not head.next:
            return None
        # 判断是否存在环
        node = self.find_circle(head)
        if not node:
            return None
        # 存在环，则设置一个从头节点开始的慢指针，两个慢指针再次相遇时即为换的入口
        s = head
        while(s!=node):
            s = s.next
            node = node.next
        return node

    #  判断是否存在环，存在则返回快慢指针相遇的节点
    def find_circle(self, head):
        f = head
        s = head
        while(f and f.next):
            s = s.next
            f = f.next.next
            if s==f:
                return s
        return None

C++实现

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        if(head==NULL) return NULL;
        // 判断是否存在环
        ListNode *node = find_circle(head);
        if(node==NULL) return NULL;
        // 设置一个从头节点开始的慢指针，两个慢指针再次相遇时即为换的入口
        ListNode *s = head;
        while(s!=node){
            s = s->next;
            node = node->next;
        }
        return node;
    }
    
    // 判断是否存在环，存在则返回快慢指针相遇的节点
    ListNode *find_circle(ListNode *head){
        ListNode * s = head;
        ListNode * f = head;
        while(f!=NULL && f->next!=NULL){
            s = s->next;
            f = f->next->next;
            if(s==f) return s;
        }
        return NULL;
    }
};