Completed
Dec 25, 2024
标签
链表
双指针
相关企业
难度
中等
- 题目描述：给定一个链表，找到其环的入口，如果没有环则返回null
- 代码思路：
- 判断是否有环：两个快慢指针分别从头节点出发，慢指针一次走一格，快指针一次走两个，如果有环，则二者一定会在环内相遇，如果没环，则快指针会先到达null处。可以类比于跑步，跑得快的会套跑的慢的一圈
- 判断环入口：快指针和慢指针相遇的时候，慢指针走了x+y步，快指针走了x+n*(y+z)步骤，n为圈数，大于等于1，如图所示，图片节选自代码随想录。因为快指针是慢指针的两倍速，所以2x+2y=x+y+n*(y+z)。化简后发现当n=1时，x=z，当n大于1时，x=z+n-1圈。也就是说，头节点到环入口的距离等于（相遇节点到环的距离或相遇节点到环的距离+n-1圈），因此，用两个指针，一个从头节点出发，一个从相遇节点出发，最终一定会相遇在环入口，无论第二个指针在环里绕了多少圈
- 第一个while循环判断是否有环
- 第二个while循环判断环入口
