美文网首页
Java实现有环的单向链表,并判断单向链表是否有环

Java实现有环的单向链表,并判断单向链表是否有环

作者: tinyvampirepudg | 来源:发表于2019-07-12 09:54 被阅读0次

Java实现有环的单向链表,并判断单向链表是否有环

有一个单向链表,链表当中有可能出现环,就像下图这样。我们如何判断一个单向链表是否有环呢?

有环的单向链表

那么第一步,我们先实现一个这样的链表,接着再说如何判断这样的链表。

实现有环的单向链表

1、定义add(Node node)方法

    /**
     * 向链表末尾添加结点
     *
     * @param node 结点的next指向为null,表示尾结点。
     * @return
     */
    public boolean add(SingleNode node) {
        if (first == null) {
            first = node;
        } else {
            SingleNode last = get(getSize() - 1);
            last.next = node;
        }
        size++;
        return true;
    }

    /**
     * 末尾添加一个特殊结点,形成一个环,为了测试用。
     *
     * @param node 这个node的next指向单项链表中已经存在的结点。
     * @return
     */
    public boolean addCycleNode(SingleNode node) {
        if (getSize() < 2) {
            return false;
        }
        SingleNode last = get(getSize() - 1);
        last.next = node;
        return true;
    }

2、先正常生成一个无环的单向链表,最后在末尾添加一个结点,让该结点的next指向前面的某个结点。

        // 循环链表
        SingleLinkedList sll = new SingleLinkedList();
        SingleNode head = new SingleNode(0, null);
        sll.add(head);
        for (int i = 1; i < 10; i++) {
            SingleNode node = new SingleNode(i, null);
            sll.add(node);
        }
        SingleNode sn = new SingleNode(111, null);
        sll.add(sn);
        for (int i = 10; i < 20; i++) {
            SingleNode node = new SingleNode(i, null);
            sll.add(node);
        }
        System.out.println(sll.toString());

输出如下:此时打印的还是一个无环单向链表。

SingleLinkedList:[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 111, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]

接着添加最后一个结点,让其next指向之前的sn结点,这样就形成了一个闭环。

        // 最后一个结点的next指向之前添加的某个结点。
        SingleNode last = new SingleNode(222, sn);
        sll.add(last);

接着打印结果:需要注意的是,这里的打印log的方法我做了处理,具体细节请查看源码。

cycle:[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 111, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 222, 111]

最后插入的结点的值为222,它的next指向的是111结点,如上所示,在222之后打印的就是111节点了,如果继续打印,就会一直循环打印下去。

判断单向链表是否有环

方法一:使用Hash Table
判断一个链表是否有环,我们只需要判断某个结点是否之前被访问过即可。这里我们优先想到的就是使用Hash表进行存储。
我们依次遍历访问每个结点,并将结点的引用存储到hash表中。如果当前结点是null,说明我们到达链表未尾部了,则当前链表一定无环;如果当前结点在hash表中已经存储过了,此时返回true即可。代码如下:

    /**
     * 判断单链表中是否有环
     * 借助HashSet来判断。
     *
     * @param head
     * @return
     */
    public boolean hasCycleByHashSet(SingleNode head) {
        Set<SingleNode> set = new HashSet<>();
        SingleNode node = head;
        while (node != null) {
            if (set.contains(node)) {
                return true;
            } else {
                set.add(node);
            }
            node = node.next;
        }
        return false;
    }

方法二:使用快慢指针
首先创建两个指针1和2(在Java里就是两个对象引用),同时指向这个链表的头结点。然后开始一个大循环,在循环体中,1每次移动一个结点,2每次移动2个结点。最后比较这两个结点指向的结点是否相同。如果相同,则判断出链表有环,如果不同,则继续下一次循环。

代码如下:

    /**
     * 判断单链表中是否有环
     * 借助快慢指针来判断。
     *
     * @param head
     * @return
     */
    public boolean hasCycleByTowPointers(SingleNode head) {
        // 排除无数据或者只有一个数据且无闭环的情况
        if (head == null || head.next == null){
            return false;
        }
        SingleNode slow =  head;
        SingleNode fast = head.next;
        while(slow != fast){
            // 判断快指针结点是否为null,如果为null,则说明到达单向链表的结尾了。
            if(fast == null || fast.next == null){
                return false;
            }
            slow = slow.next;
            fast = fast.next.next;
        }
        return true;
    }

完整代码请查看

项目中搜索SingleLinkedList即可。

github传送门 https://github.com/tinyvampirepudge/DataStructureDemo

gitee传送门 https://gitee.com/tinytongtong/DataStructureDemo

参考:

1、linked-list-cycle

2、漫画算法:如何判断链表有环?

3、使用Java实现单向链表,并完成链表反转。

相关文章

  • Java实现有环的单向链表,并判断单向链表是否有环

    Java实现有环的单向链表,并判断单向链表是否有环 有一个单向链表,链表当中有可能出现环,就像下图这样。我们如何判...

  • 数据结构-链表

    相关掌握点 单向链表 双向链表 反转单向链表 判断链表是否含有环 链表构建 链表是一种线性结构,是通过指针引用节点...

  • 判断链表是否有环

    有一个单向链表,链表中有可能出现“环”,就像下图这样。那么,如何用程序来判断该链表是否为有环链表呢? 首先创建两个...

  • 链表-链表有环问题

    1. 判断一个单向链表是否有环 有环的链链表大概张这样 有环的链表和普通的链表的区别就是尾指针指向了链表中的某一个...

  • 链表

    单向链表 链表反转 判断是否有环,找链表的中间节点 快慢指针 找环的入口(求两个链表的交点可以转化成这个问题) p...

  • 两个无限长度链表(也就是可能有环) 判断有没有交点

    给定单链表,检测是否有环。如果有环,则求出进入环的第一个节点。 判断单向链表是否有环,可以采用快指针与慢指针的方式...

  • 链表面试常见合集

    给定单链表,检测是否有环。如果有环,则求出进入环的第一个节点。 判断单向链表是否有环,可以采用快指针与慢指针的方式...

  • 链表

    现在有一个单向链表,谈一谈,如何判断链表中是否出现了环 考察点:链表参考回答:单链表有环,是指单链表中某个节点的n...

  • 单向链表-链表有环判断

    今天学习的算法是链表有环判断,这个题目的重点主要找到解题思路上面,下面让我们一起看看怎么实现吧。 题目介绍 给定一...

  • 小灰算法(一): 快慢指针求解链表是否有环

    文章参考自书籍:《漫画算法-小灰的算法之旅》-魏梦舒 如图是一个有环的单向链表,那么我们如何判断一个单向链表有环吗...

网友评论

      本文标题:Java实现有环的单向链表,并判断单向链表是否有环

      本文链接:https://www.haomeiwen.com/subject/tvwhkctx.html