上海企业微信网站制作/关键词优化话术

题目转载自：力扣

分析： 

这一题题目要求使用O（1）的时间复杂度来解。

然后大概有两种解法来做，下面分别来介绍一下：

首先判断链表是否有环，如果有环的话，先将指针定位到环内（可以通过快慢指针来将两个指针在环内相遇，这样就能定位到环内的结点了）。

在拿到环内结点的情况下有以下两种方法来解题：

1.因为是一个环，所以我们可以分别指向环内的每个点，然后在确定了环内固定点之后这里用P1代表环内的固定点，声明一个指针指向链表头部这里用P2代表头结点，然后P2移动每次前移一步，P1不动，用一个整型变量来记录P2移动的步数，当P2和P1相遇时，步数记录停止，然后该步数就是P2头结点到环内节点的一个距离；下面要做的就很简单了，我们只需要遍历环内的结点，分别求一下头节点到环内节点的距离即可，最小距离就是这个入环点。

public class Solution {public static ListNode detectCycle(ListNode head) {if (head == null) {return null;}ListNode fastNode = head;ListNode slowNode = head;ListNode inCycleNode = null;while (slowNode != null) {fastNode = fastNode.next;slowNode = slowNode.next;if (slowNode == null) {break;}slowNode = slowNode.next;if (slowNode != null) {if (fastNode == slowNode) {inCycleNode = fastNode;break;}} else {break;}}if (inCycleNode == null) {return null;}ListNode res = null;int len = Integer.MAX_VALUE;ListNode node = inCycleNode;do {ListNode temp = head;int tempRes = 0;while (temp != node) {tempRes++;temp = temp.next;}if (tempRes < len) {res = temp;len = tempRes;}node = node.next;} while (node != inCycleNode);return res;}public static void main(String[] args) {ListNode first = new ListNode(3);ListNode second = new ListNode(2);ListNode third = new ListNode(0);ListNode fourth = new ListNode(-4);first.next = second;second.next = third;third.next = fourth;fourth.next = second;ListNode listNode = detectCycle(first);}
}

2.第二种解法偏向于数学了，这里我就不把具体的解法贴出来了，具体解法分析如下图（截图自力扣官方解答），但是我会分析一下我看的这个解答分析里的疑问点，如下：

 这里我要解释的只有一点：

为什么快指针和慢指针相遇的时候，慢指针走的距离不大于一圈（即小于等于一圈），这也跟上述分析的论点契合，因为上述分析就是默认两个指针在环内相遇的时候，慢指针在环内走的记录小于等于一圈，下面是解释：

因为快指针每次走两步，慢指针每次走一步，所以可以理解为慢指针不动，快指针每次走一步，假设快慢指针在环内同一点往后移动，这个时候快指针需要走的路程最长才可以追上慢指针（如果快慢指针不在同一个结点，那么快指针追上慢指针需要走的路程将会缩短），假设环有n个结点，快指针需要走n次，才能与慢指针相遇，此时慢指针恰好走了一圈，这个是最慢可以追上慢指针的情况，其他情况，快指针不用走n次就可以追上慢指针了，所以上图分析里的公式是对的。

public class Solution {public ListNode detectCycle(ListNode head) {if (head == null) {return null;}ListNode slowPointer = head;ListNode fastPointer = head;ListNode meetPos = null;while (fastPointer != null) {fastPointer = fastPointer.next;if (fastPointer == null) {break;}slowPointer = slowPointer.next;fastPointer = fastPointer.next;if (fastPointer == null) {break;}if (slowPointer == fastPointer) {meetPos = slowPointer;break;}}if (meetPos == null) {return null;}ListNode res = head;while (res != meetPos) {res = res.next;meetPos = meetPos.next;}return res;}public static void main(String[] args) {}
}