侧边栏壁纸
博主头像
惊羽博主等级

hi ,我是惊羽,前生物学逃兵,现系统工程沉迷者 . 贝壳签约工程师 , 曾被雇佣为 联拓数科 · 支付研发工程师 、京东 · 京东数科 · 研发工程师、中国移动 · 雄安产业研究院 · 业务中台技术负责人 .

  • 累计撰写 100 篇文章
  • 累计创建 14 个标签
  • 累计收到 9 条评论

算法练习(12) - 判断单链表是否有环

惊羽
2021-06-22 / 0 评论 / 0 点赞 / 116 阅读 / 310 字 / 正在检测是否收录...
温馨提示:
本文最后更新于 2021-11-05,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题目

给定一个链表,判断链表中是否有环。

答案

public class Solution {
    public boolean hasCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        int i = 1;
        while(fast != null ){
            i = -i;
            if(i>0){
                slow = slow.next;
            }
            fast = fast.next;
            if(slow == fast){
                return true;
            }
        }
        return false;
    }
}

思路

使两个指针同时从头结点出发,快指针每一次循环都往下走一步,慢指针隔一次走一步,成环后由于两个指针会打转,两个指针步长一致,快的一定会追上慢的,并且在同一个节点上;

0
广告 广告

评论区