判断单链表中是否有环

楚天乐 88 0 条

算法核心思想

设置两只小狗,一个速度为1,另一只速度为2。小学相遇问题,很简单对吧。如果有环,第二只狗出发之后会追上第一只狗

退出条件

  • 到达链表尾部
  • 避免空指针

实现代码

public class Solution {
    public boolean hasCycle(ListNode head) {
        ListNode dog1 = head; // 狗1
        ListNode dog2 = head; // 狗2

        // 空指针判断
        if(dog1 == null || dog2 == null){
            return false;
        }

        // 退出条件: 空指针
        while(dog1.next != null && dog2.next != null && dog2.next.next != null){
            dog1 = dog1.next;
            dog2 = dog2.next.next;

            // 相遇,有环
            if(dog1 == dog2){
                return true;
            }
        }

        return false;
    }
}

打赏

微信打赏

支付宝打赏



发表我的评论
昵称 (必填)
邮箱 (必填)
网址
执行时间: 53.192138671875 毫秒