java实现单链表中是否有环的方法详解
这是一道微软经典笔试题,就是两个指针h1,h2都从头开始遍历单链表,h1每次向前走1步,h2每次向前走2步,如果h2碰到了NULL,说明环不存在;如果h2碰到本应在身后的h1说明环存在(也就是发生了套圈)。 如果环不存在,一定是h2先碰到NULL: 复制代码 代码如下: package org.myorg; public class Test{ public static boolean isExsitLoop(SingleList a) { Node<T> slow = a.head; Node<T> fast = a.head; while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; if (slow == fast) return true; } return false; }
public static void main(String args[]){ 复制代码 代码如下: package org.myorg; public class Node{ public Object data; //节点存储的数据对象 public Node next; //指向下一个节点的引用 public Node(Object value){ 复制代码 代码如下: package org.myorg; public class SingleList{ private int size; private Node head;
public SingleList(){
(编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |