【算法题】链表中环的入口结点

这题要找出链表中环的入口，如果链表中没有环，则返回空。前面我们讲过《判断链表是否有环》，所以我们可以根据前面的解来判断链表是否有环，如果没环，自然就不可能有环的入口。如果有环我们再来找出环的入口，怎么找呢？如下图所示。

在相遇点快指针走过的距离是： a+c+(b+c)*m，其中 b+c 是环的周长， m 是快指针在环上转了 m 圈之后和慢指针相遇。慢指针走过的距离是： a+c+(b+c)*n，其中 n 是慢指针在环上转了 n 圈之后和快指针相遇，很明显 n < m 。

由于快指针每次走两步，慢指针每次走一步，所以快指针走的距离是慢指针的 2 倍，也就是：

a+c+(b+c)*m = 2*(a+c+(b+c)*n)

整理之后可以得到：a+c= (b+c)*(m-2*n)，也就是说 a+c 的长度等于 (m-2*n) 个环的长度。在整理一下又可以变成：

a = (b+c)*(m-2*n-1)+b。其中 (b+c)*(m-2*n-1) 是在环上走了整整 (m-2*n-1) 圈。

这个时候如果我们使用两个指针，一个从起始位置开始，一个从相遇点开始，每次都走一步，最终它们一定会在环的入口相遇。

    public ListNode EntryNodeOfLoop(ListNode pHead) {
        ListNode slow = pHead;// 快指针
        ListNode fast = pHead;// 慢指针
        while (fast != null && fast.next != null) {
            // 快慢指针，快指针每次走两步，慢指针每次走一步
            fast = fast.next.next;
            slow = slow.next;
            if (slow == fast) {// 如果相遇，说明有环
                // 确定有环之后才能找环的入口
                while (pHead != slow) {
                    // 两指针，一个从头结点开始，一个从相遇点
                    // 开始每次走一步，直到再次相遇为止
                    pHead = pHead.next;
                    slow = slow.next;
                }
                return slow;
            }
        }
        return null;
    }

public:
    ListNode *EntryNodeOfLoop(ListNode *pHead) {
        ListNode *slow = pHead;// 快指针
        ListNode *fast = pHead;// 慢指针
        while (fast && fast->next) {
            // 快慢指针，快指针每次走两步，慢指针每次走一步
            fast = fast->next->next;
            slow = slow->next;
            if (slow == fast) {// 先判断是否有环，
                // 确定有环之后才能找环的入口
                while (pHead != slow) {
                    // 两指针，一个从头结点开始，一个从相遇点
                    // 开始每次走一步，直到再次相遇为止
                    pHead = pHead->next;
                    slow = slow->next;
                }
                return slow;
            }
        }
        return nullptr;
    }

各大厂算法面试题已经整理好了，请看这里：《算法专栏》