环形链表 II

https://leetcode.cn/problems/linked-list-cycle-ii/description/

image.png

        # 快慢指针,慢指针每次一步，快指针每次两步
        # 由题可知：两个指针相遇一定是在环内，相遇时的慢指针一定未走完一环
        # 快指针已经走完k环
            # 证明：假设环的长度为n，在slow指针进环时（slow在环入口），fast离slow最大距离为n-1（即刚进环一步），快慢指针每移动一次，fast就离slow更近一步，所以最多最多n-1次fast就会追上slow，此时slow才走了n-1步。所以在slow还没走完一圈的时候，肯定会被追上
        # 设：从头结点到入环点的距离为a，入环点到相遇点的距离为b，
        # 相遇点到入环点的距离为c；环长即为 b + c
        # 所以：慢指针走的路程：a + b
        #      快指针走的路程：a + b + k * (b + c)
        # 又因为快指针的速度是慢指针的两倍,那么时间相同时，路程也是两倍
        # 所以：2 * (a + b) = a + b + k * (b + c) =>
        #    a + a + b + b = a + b + b + c + (k - 1) * (b + c) =>
        #                a = c + (k - 1) * (b + c)
        # 即：从头结点到入环点的距离等于从相遇点到入环点的距离加上k-1倍环长距离
        # 当快慢指针相遇时，让头结点与慢指针同时向后一步步走
        # 那么两个指针一定会在入环点相遇

    ListNode *detectCycle(ListNode *head) {
        ListNode *slow = head, *fast = head;
        while (fast) {
            slow = slow -> next;
            fast = fast -> next;
            if (fast == NULL) {
                return NULL;
            }
            fast = fast -> next;
            if (slow == fast) {
                break;
            }
        }
        if (fast == NULL) {
            return NULL;
        }
        while (head != fast) {
            head = head -> next;
            fast = fast -> next;
        }
        return head;
    }