源码网商城,靠谱的源码在线交易网站 我的订单 购物车 帮助

源码网商城

java实现单链表中是否有环的方法详解

  • 时间:2022-02-26 04:27 编辑: 来源: 阅读:
  • 扫一扫,手机访问
摘要:java实现单链表中是否有环的方法详解
这是一道微软经典笔试题,就是两个指针h1,h2都从头开始遍历单链表,h1每次向前走1步,h2每次向前走2步,如果h2碰到了NULL,说明环不存在;如果h2碰到本应在身后的h1说明环存在(也就是发生了套圈)。     如果环不存在,一定是h2先碰到NULL:     如果环存在,h2与h1一定会相遇,而且相遇的点在环内:h2比h1遍历的速度快,一定不会在开始的那段非环的链表部分相遇,所以当h1,h2都进入环后,h2每次移动都会使h2与h1之间在前进方向上的差距缩小1,最后,会使得h1和h2差距减少为0,也即相遇
[u]复制代码[/u] 代码如下:
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[]){     SingleList list = new SingleList();     for(int i=0;i<100;i++){       list.add(i); } System.out.print(SingleList.isExistingLoop(list)); } }
[u]复制代码[/u] 代码如下:
package org.myorg; public class Node{     public Object data; //节点存储的数据对象     public Node next; //指向下一个节点的引用     public Node(Object value){         this.data = value;    }     public Node(){       this.data = null;           this.next = null;    } }
[u]复制代码[/u] 代码如下:
package org.myorg; public class SingleList{     private int size;     private Node head;     private void init(){         this.size = 0;         this.head = new Node();      }    public SingleList(){          init();    }   public boolean contains(Object value){    boolean flag = false;    Node p = head.next;    while(p!=null){         if(value.equals(p.data)){            flag = true;            break;        }else(             p = p.next;            )      }     return flag;   }     public boolean add(Object value){      if(contains(value))          return false;      else{      Node p = new Node(value);      p.next=head.next;      head.next = p;      size++; }   return true;     } }
  • 全部评论(0)
联系客服
客服电话:
400-000-3129
微信版

扫一扫进微信版
返回顶部