23. 链表中环的入口结点

文档摘要

链表中环的入口结点 NowCoder 题目描述一个链表中包含环，请找出该链表的环的入口结点。要求不能使用额外的空间。解题思路使用双指针，一个快指针 fast 每次移动两个节点，一个慢指针 slow 每次移动一个节点。因为存在环，所以两个指针必定相遇在环中的某个节点上。假设环入口节点为 y1，相遇所在节点为 z1。假设快指针 fast 在圈内绕了 N 圈，则总路径长度为 x+Ny+(N-1)z。z 为 (N-1) 倍是因为快慢指针最后已经在 z1 节点相遇了，后面就不需要再走了。而慢指针 slow 总路径长度为 x+y。因为快指针是慢指针的两倍，因此 x+Ny+(N-1)z = 2(x+y)。