1.题目描述        

        给定一个链表的头节点  head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

不允许修改 链表。

提示：

• 链表中节点的数目范围在范围 [0, 104] 内
• -105 <= Node.val <= 105
• pos 的值为 -1 或者链表中的一个有效索引

2.解决思路

        这道题目相比上一道题目，要求有一些变化，现在我们需要返回链表入环的点。所以上一道题的解法不能够复用，因为我们并不知道他们在哪个位置相遇。

        为了完成这道题目，可以这样思考，因为首先要找到相遇点，所以不可避免我们还是要用到快慢指针，而解题的关键就是如何判断相遇点的位置关系。

        设链表中环外部分的长度为 a。slow 指针进入环后，又走了 b 的距离与 fast 相遇。此时，fast 指针已经走完了环的 n 圈，因此它走过的总距离为 a+n(b+c)+b=a+(n+1)b+nc。

，任意时刻，fast 指针走过的距离都为 slow 指针的 2 倍。因此，我们有

                                a+(n+1)b+nc=2(a+b)⟹a=c+(n−1)(b+c)
有了 a=c+(n−1)(b+c) 的等量关系，我们会发现：从相遇点到入环点的距离加上 n−1 圈的环长，恰好等于从链表头部到入环点的距离。

所以也就是：相遇点距离入环点的距离就等于头结点距离入环点的距离

3.步骤讲解

        1.因为快指针的存在，先判断链表长度，小于两个节点则返回null

        2.定义三个节点，同时指向头结点，其中pre用于最后一步找入环点位置，其余两个是快慢指针

        3.进行循环，条件是遍历不到空，也就是不为无环链表时进行循环。

        4.先让慢指针移动一步，然后判断快指针的下一个节点是否为空，为空返回null，反之快指针移动两个节点

        5.当快慢指针相遇时，进行第二步操作，经过上述分析，可知此时让指向头结点的pre指针与慢指针slow同时开始移动，他们相遇的位置就是入环点。返回pre即可

4.代码展示

class ListNode {int val;ListNode next;ListNode(int x) {val = x;next = null;}}public ListNode hasCycle(ListNode head) {if (head == null || head.next == null){return null;}ListNode pre = head;ListNode slow = head;ListNode fast = head;while (fast != null){slow = slow.next;if (fast.next != null){fast = fast.next.next;} else {return null;}if (slow == fast){while (pre != slow){pre = pre.next;slow = slow.next;}return pre;}}return null;}

5.执行结果

在leetcode中测试用例平均耗时0ms

内存分布43.86MB