142、环形链表||

题意: 给定一个链表,返回链表开始入环的第一个节点。 如果链表无环,则返回 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;
    }
}

上一篇:142. 环形链表 II


下一篇:leetcode_142环形链表II