题意: 给定一个链表,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。
为了表示给定链表中的环,使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没有环。
进阶挑战:不允许修改给定的链表。
方法:快慢指针(双指针)
public class Huanxinglianbiao2 {
public ListNode detectCycle(ListNode head){
//设置快慢指针
ListNode fast = head;
ListNode slow = head;
while(fast!=null && fast.next!=null){
//快指针走两步
//慢指针走一步
fast = fast.next.next;
slow = slow.next;
//如果fast == slow确认有环
//找到快慢指针的相遇点,再相遇点快指针回到head,慢指针保持不动
//他们再以相同的速度前进,当他们再次相遇的点,就是环形入口的入口点了
if (fast == slow){
fast = head;
while (fast!=slow){
fast = fast.next;
slow = slow.next;
}
//返回环的入口
return fast;
}
}
//遍历链表结束,没有找到环,则返回空;
return null;
}
}