环形链表.找到入环节点

LeetCode 142：环形链表II 可以在这里测试

题目描述

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

示例1：
在这里插入图片描述

输入：head = [1,2], pos = 0
输出：返回索引为 0 的链表节点
解释：链表中有一个环，其尾部连接到第一个节点。

示例2：
在这里插入图片描述

输入：head = [1,2], pos = 0
输出：返回索引为 0 的链表节点
解释：链表中有一个环，其尾部连接到第一个节点。

示例3：
在这里插入图片描述

输入：head = [1], pos = -1
输出：返回 null
解释：链表中没有环。

解题思路

这里用到一个小技巧，快慢指针法：
1.环形链表没有尾结点，会在环里循环，因此，如果能走到null ，就表示无环，
2.有环时，使用快慢指针法，快指针一次走两步，慢指针一次走一步，一定会在环内相遇，
3.相遇后，快指针回到头节点，然后改成每次走一步，慢指针还是走一步。然后就会在入环节点相遇。
4.上面的结论，自己可以试着证明下。

代码如下：

/*** Definition for singly-linked list.* class ListNode {*     int val;*     ListNode next;*     ListNode(int x) {*         val = x;*         next = null;*     }* }*/
public class Solution {public ListNode detectCycle(ListNode head) {//环形链表 没有null 节点，如果走到null 说明无环，if(head == null || head.next == null || head.next.next == null){return null;}//快的先走两步，慢的走一步ListNode fast = head.next.next;ListNode slow = head.next;//先让快慢指针相遇while(fast != slow){//遇到null 说明无环if(fast.next == null || fast.next.next == null){return null;}fast = fast.next.next;slow = slow.next;}//快指针回到头节点，开始一次走一步，就会在入环节点相遇fast = head;while(fast != slow){fast = fast.next;slow = slow.next;}return slow;}
}