前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >算法练习(7)-判断单链表是否有环,以及求环的长度

算法练习(7)-判断单链表是否有环,以及求环的长度

作者头像
菩提树下的杨过
发布2021-04-01 09:44:56
4750
发布2021-04-01 09:44:56
举报
文章被收录于专栏:菩提树下的杨过

如果面试时,遇到这个题目,先喝口水压压惊,回想一下,咱们小时候念小学时,数学老师最喜欢的一类题目:

跑道上,2个运动员,1个速度是3m/s,1个速度是5m/s,同一起点起跑后,多久运动员2会再次遇到运动员1?是不是感觉异曲同工? 这2个速度不同的运动员,相当于就是快/慢2个指针

代码语言:javascript
复制
@Data
class Node {
    private String value;
    private Node next;

    public Node(String value) {
        this.value = value;
    }
}

@Test
public void isLoopLink() {
    Node a = new Node("a");
    Node b = new Node("b");
    Node c = new Node("c");
    Node d = new Node("d");
    a.next = b;
    b.next = c;
    c.next = d;
    d.next = b;

    int loopSize = 0, meetCount = 0;
    Node slow = a, fast = a;
    while (slow.next != null) {
        fast = fast.next.next;
        slow = slow.next;
        if (fast == null || slow == null) {
            System.out.println("it is not a loop link");
            break;
        }
        if (fast.value.equalsIgnoreCase(slow.value)) {
            //首次相遇
            meetCount += 1;
            if (meetCount > 1) {
                //再次相遇
                System.out.println("it is a loop link,loopSize:" + loopSize);
                break;
            }
        }
        if (meetCount == 1) {
            //首次遇到后,开始数环的节点个数
            loopSize += 1;
        }
    }
}
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2021-03-27 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档