算法与数据结构——判断链表中是否有环

package com.lxd.leetcode.demo; import com.sun.org.apache.xerces.internal.dom.PSVIAttrNSImpl; import java.util.HashSet; import java.util.Set; /** * @author lxd * @version 1.0.0 * @create 2020-07-01 17:50 * @desc 链表中是否有环 **/ public class LinkedHashLoopDemo { private static class LinkNode<T>{ private LinkNode next; private T data; public LinkNode(T data){ this.data=data; } } /*** * 快慢两个指针，同时从头结点出发，如果又环，必然会相遇 * @param head * @return */ private static boolean isCircle(LinkNode head){ if(head==null){ return false; } LinkNode fast = head; LinkNode slow = head; while (fast!=null&&fast.next!=null){ fast = fast.next.next; slow = slow.next; if(fast == null){ return false; } if(fast==slow){ return true; } } return false; } /** * 遍历链表，将链表节点存放到set中，如果有节点 * @param head * @return */ private static boolean isCircle2(LinkNode head){ if(head==null || head.next==null){ return false; } Set<LinkNode> nodeSet =new HashSet<>(); while (head!=null){ if(nodeSet.contains(head)){ return true; } else { nodeSet.add(head); } head= head.next; } return false; } public static void main(String[] args) { LinkNode<String> head= new LinkNode<>("我"); head.next=new LinkNode<>("我"); LinkNode<String> circleNode= new LinkNode<>("我"); head.next.next=circleNode; head.next.next.next=new LinkNode<>("我"); head.next.next.next.next=circleNode; System.out.println(isCircle(head)); System.out.println(isCircle2(head)); } }