[M链表] lc142. 环形链表 II(快慢指针+数学推导+基础题)

1. 题目来源

链接：142. 环形链表 II

相关题：

• [E链表] lc141. 环形链表(快慢指针+基础题)

题单：

• 11. 链表、二叉树与一般树（前后指针/快慢指针/DFS/BFS/直径/LCA）
  • §1.6 快慢指针

2. 题目解析

这个是很经典的题目哈，简单做的话，直接上哈希表就完事了。反正只会有一个环节点，但实际上背后隐藏着数学做法，可以尝试推导一下。

思路：

• 记：head 到环入口长度为 a，入口到快慢指针环内相遇点长度为b，快慢指针环内相遇点到入口长度为 c。
• 首先，当快慢指针相遇时，慢指针所走步数没有超过环的长度。
  • 采用相对速度分析：慢指针不动，快指针每次走 1 步，最坏情况下慢指针在环的入口，而快指针在环的入口下一个位置。那么此时快指针仅需 环长-1 步就可以遇到慢指针。而其他情况下，均小于此长度。
• 故：从移动距离分析：
  • 慢指针：a+b
  • 快指针：a+k(b+c)
• 快指针移动速度是慢指针两倍，则有：2(a+b)=a+k(b+c) 故有，a-c=(k-1)(b+c)。
• 其实可以发现，a-c 这一段是头结点减去快慢指针相遇点到入口点的距离。这段距离等于 (k-1)倍 环的长度。
• 那么也就是说，当快慢指针相遇时，此时慢指针和头结点一起再向前走 c 步，然后慢节点将到达环的入口点，头结点所处位置到环的入口点距离等于 (k-1)倍环长。故只需要一直走，那么头结点和慢指针就能在环的入口点位置相遇，此时该点即为环的入口点。

• 时间复杂度：$O(n)$
• 空间复杂度：$O(1)$

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        auto a = head, b = head;
        while (b && b->next) {
            a = a->next;
            b = b->next->next;
            if (a == b) {
                while (head != a) head = head->next, a = a->next;
                return a;
            }
        }

        return NULL;
    }
};