如何判断单向链表有环?
|
前言：链表在开发过程中属于出现频次十分高的一种数据结构，在java中,比如我们熟知的LinkedList、HashMap底层结构、LinkedHashMap、AQS等都使用到了链表,关于单向链表有几个经典问题?1:如何判断链表有环? 2:如果有环,找出入环的节点 3:环的长度是多少？本篇博客就围绕这三个问题来展开讨论 目录 一:如何判断单向链表有环？ 二:如果有环,找出入环的节点 三:环的长度是多少？ 四:测试 五:总结 问题一：如何判断单向链表有环？ 首先我们来画一个普通的单向链表和环状链表的结构图：
? ? 可以看出在环形单向链表的EFGH形成了一个环状,那么如何用程序判断它成环呢？ 这里要借助一个跑道的思想：假如有一个环形的跑道，跑道上有两个人P和Q,假设P的速度是1km/10分钟，Q的速度是2km/10分钟,速度恒定不变。如果这个跑道是环型的,他们同时出发,起初Q领先,而在某一个时刻，Q终将从后面追上过P,他们两一定会相遇,而如果是直线跑道,P和Q一定不会相遇。借助于这个思想，我们可以设置快慢指针去绕着环状链表去走，如果两个指针相遇，那么它肯定是环形的。
? ? 下面是java版的实现：通过设定两个不同速度的快慢指针来遍历整个链表，如果快慢相遇，则整个链表一定有环：
? ? ? 程序的具体实现: /** * 链表节点 */ public static class Node { private String value; Node next; public String getValue() { return value; } void setValue(String value) { this.value = Node getNext() { next; } setNext(Node next) { this.next = next; } } /** * 链表是否有环 * @param sourceNode * @return boolean hasCircle(Node sourceNode) { if (sourceNode == null) { return false; } if (sourceNode.next == //慢指针 Node slowPointer = sourceNode; 快指针 Node fastPointer =while (fastPointer != ) { 慢指针每次走一个链表格 slowPointer = slowPointer.next; 快指针每次走两个链表格 fastPointer = fastPointer.next.next; if (slowPointer == fastPointer) { true; } } ; } ? 问题二:如果有环,找出入环的节点 ? ?假设环形链表的长度是L,相遇点在M,在相遇之后，只需要将fast指针指向开始的节点，然后和slow指针保持同一的速度遍历(相当于此时不分快慢,每个指针的每次步长为1),下一次两个节点相遇的时候就是链表的环形入口：关于此结论的数学证明： ? ?https://zhuanlan.zhihu.com/p/33663488?（在此感谢博主的同意）
? ? 程序实现如下： /** * 获取入口节点 * static Node getEnterNode(Node sourceNode) { ) { slowPointer = slowPointer.next; fastPointer =break; } } System.out.println("相遇点"+fastPointer.getValue()); fastPointer =) { fastPointer = fastPointer.next; slowPointer =if (fastPointer == slowPointer) { fastPointer; } } ; } ? 问题三:环的长度是多少？ ? ?这个问题比较简单，既然我们已经知道了环的入口节点，只需要新增一个指针，顺着环依次循环一遍用一个变量进行累加,每次的步长设为一,然后直到和入口节点相遇(环入口的节点位置保持不变)那么环的长度也就统计出来了:
? ??程序具体实现: * 获取环的长度 * * int getCirCleLength(Node sourceNode) { return 0final Node enterNode = getEnterNode(sourceNode); 环的下一个指针 Node cirCleSecondNode = enterNode.next; int lenght = 1; while (cirCleSecondNode != enterNode) { lenght++; cirCleSecondNode = cirCleSecondNode.next; } lenght; } ? ?四：测试 我们来写一个测试方法来模拟一下上面的环状节点，然后测试一下： main(String[] args) { final Node node = new Node(); node.setValue("A"); final Node node2 = Node(); node2.setValue("B"final Node node3 = Node(); node3.setValue("C"final Node node4 = Node(); node4.setValue("D"final Node node5 = Node(); node5.setValue("E"final Node node6 = Node(); node6.setValue("F"final Node node7 = Node(); node7.setValue("G"final Node node8 = Node(); node8.setValue("H"); node.setNext(node2); node2.setNext(node3); node3.setNext(node4); node4.setNext(node5); node5.setNext(node6); node6.setNext(node7); node7.setNext(node8); node8.setNext(node5); final boolean hasCircle = hasCircle(node); System.out.println("是否是环形链表:"+hasCircle); getEnterNode(node); System.out.println("相遇节点是:"+enterNode.getValue()); int cirCleLength = getCirCleLength(node); System.out.println("环状长度:"+cirCleLength); } ? 程序输出如下：
? ?五:总结 ? 本次主要分析了环形链表的一些问题,并给出了示例代码，通过此篇博客可以学习到关于链表的一些东西，快慢指针的基本思想，以及如何求相遇节点和环的长度两个问题，如何用java求解,并熟悉链表这种数据结构，在实际工作中可以加深对环形链表的一些理解。 ? 最后: 如果对学习java有兴趣可以加入群:618626589,本群旨在打造无培训广告、无闲聊扯皮、无注水斗图的纯技术交流群，群里每天会分享有价值的问题和学习资料,欢迎各位随时加入? ? （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
