07.判断单链表是否有环

目录介绍

  • 01.题目要求
  • 02.问题分析
  • 03.实例代码

好消息

  • 博客笔记大汇总【15年10月到至今】，包括Java基础及深入知识点，Android技术博客，Python学习笔记等等，还包括平时开发中遇到的bug汇总，当然也在工作之余收集了大量的面试题，长期更新维护并且修正，持续完善……开源的文件是markdown格式的！同时也开源了生活博客，从12年起，积累共计N篇[近100万字，陆续搬到网上]，转载请注明出处，谢谢！所有博客陆续更新到GitHub上！
  • 链接地址：https://github.com/yangchong211/YCBlogs
  • 如果觉得好，可以star一下，谢谢！当然也欢迎提出建议，万事起于忽微，量变引起质变！

01.题目要求

  • 这里也是用到两个指针，如果一个链表有环，那么用一个指针去遍历，是永远走不到头的。

02.问题分析

  • 用两个指针去遍历：first指针每次走一步，second指针每次走两步，如果first指针和second指针相遇，说明有环。时间复杂度为O (n)。

03.实例代码

  • 代码如下所示
    public class LinkList {
    public Node head;
    public Node current;

    //方法：向链表中添加数据
    public void add(int data) {
        //判断链表为空的时候
        if (head == null) {//如果头结点为空，说明这个链表还没有创建，那就把新的结点赋给头结点
            head = new Node(data);
            current = head;
        } else {
            //创建新的结点，放在当前节点的后面（把新的结点合链表进行关联）
            current.next = new Node(data);
            //把链表的当前索引向后移动一位
            current = current.next;
        }
    }


    //方法重载：向链表中添加结点
    public void add(Node node) {
        if (node == null) {
            return;
        }
        if (head == null) {
            head = node;
            current = head;
        } else {
            current.next = node;
            current = current.next;
        }
    }


    //方法：遍历链表（打印输出链表。方法的参数表示从节点node开始进行遍历
    public void print(Node node) {
        if (node == null) {
            return;
        }
        current = node;
        while (current != null) {
            System.out.println(current.data);
            current = current.next;
        }
    }

    //方法：检测单链表是否有环
    public boolean hasCycle(Node head) {
        if (head == null) {
            return false;
        }
        Node first = head;
        Node second = head;
        while (second != null) {
            first = first.next;  //first指针走一步
            second = second.next.next;  //second指针走两步

            if (first == second) {  //一旦两个指针相遇，说明链表是有环的
                return true;
            }
        }
        return false;
    }

    class Node {
        //注：此处的两个成员变量权限不能为private，因为private的权限是仅对本类访问。
        int data; //数据域
        Node next;//指针域

        public Node(int data) {
            this.data = data;
        }
    }
}
  • 测试代码
    public void test() {
    LinkList list = new LinkList();
    //向LinkList中添加数据
    for (int i = 0; i < 4; i++) {
        list.add(i);
    }
    //将头结点添加到链表当中，于是，单链表就有环了。
    //备注：此时得到的这个环的结构，是下面的第8小节中图1的那种结构。
    list.add(list.head);  
    System.out.println(list.hasCycle(list.head));
}

其他内容

01.关于博客汇总链接

02.关于我的博客

  • 我的个人站点：
  • github：https://github.com/yangchong211
  • 知乎：https://www.zhihu.com/people/yczbj/activities
  • 简书：http://www.jianshu.com/u/b7b2c6ed9284
  • csdn：http://my.csdn.net/m0_37700275
  • 喜马拉雅听书：http://www.ximalaya.com/zhubo/71989305/
  • 开源中国：https://my.oschina.net/zbj1618/blog
  • 泡在网上的日子：http://www.jcodecraeer.com/member/content_list.php?channelid=1
  • 邮箱：yangchong211@163.com
  • 阿里云博客：https://yq.aliyun.com/users/article?spm=5176.100- 239.headeruserinfo.3.dT4bcV
  • segmentfault头条：https://segmentfault.com/u/xiangjianyu/articles
  • 掘金：https://juejin.im/user/5939433efe88c2006afa0c6e
贡献者: yangchong211