链接：
剑指Offer 22
题目：
给定一个链表，返回链表开始入环的第一个节点。 从链表的头节点开始沿着 next 指针进入环的第一个节点为环的入口节点。如果链表无环，则返回 null。
方法一：快慢指针
分成两步，
第一步：先使用快慢指针法判断链表是否成环，若不成环则返回null；成环则进行下一步
第二步：若成环，则再建立一个新的慢指针temp从head出发，slow继续从之前快慢指针重合的位置出发，两个步长为1的指针一定会相遇！相遇的位置就是环的入口！
public class Solution {
public ListNode detectCycle(ListNode head) {
//先判断是否成环
ListNode fast=head;
ListNode slow=head;
boolean flag=false; //打一个标记
//第一次循环，确认链表是否为环，为环则找到slow和fast指针的重合位置
while(fast!=null&&fast.next!=null){ // 循环查找重合位置
fast=fast.next.next; //一次移动两个元素
slow=slow.next; //一次移动一个元素
if(fast==slow){
flag=true; //改变标记，表示成环
break; //相遇即成环，跳出while
}
}
if(flag){//如果成环
ListNode temp=head;//如果成环，再新建一个慢指针temp，从head开始移动
//第二次循环，找到换入口
while(temp!=slow){ // 循环查找入口
temp=temp.next;
slow=slow.next;
}
return temp; //重合后跳出循环，返回重合的位置
}else{//如果a=false,不成环 返回null
return null;
}
}
}
这里可以将fast反复利用，而不创建temp
注意：
- 判断成环的条件是
while(fast!=null&&fast.next!=null)如果仅写成fast!=null， 则进入循环后，由fast=fast.next.next 会出现null.next 即空指针异常！ - 如果成环，在找入口时，不能以
if(fast==slow)来判断，当输入链表只有一个节点时，满足条件但不成环！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/89382.html
