Java实现链表中环的检测

链表中环的检测，就是判断链表中是否存在环形结构。带有环形结构的链表如下图所示：

image.png

这里提供两种解决方法，判断链表中是否含有环形结构：

第一种：快慢指针法

思路：
有两个指针p1和p2，同时从头结点往下遍历链表中的所有结点。
p1是慢指针，一次遍历一个结点。
p2是快指针，一次遍历两个结点。
如果链表中没有环，p1和p2会先后遍历玩所有结点。
如果链表中有环，p1和p2会先后进入环中，一直在循环，并且一定会在某一次遍历中相遇。
因此，我们只要发现了p1和p2相遇了，就可以判断链表中一定存在环。

image.png

Java代码实现：

public class LinkADT<T> {

    /**
     * 单链表节点
     */
    private static class SingleNode<T> {
        public SingleNode<T> next;
        public T data;

        public SingleNode(T data) {
            this.data = data;
        }

        public T getNextNodeData() {
            return next != null ? next.data : null;
        }
    }

    /**
     * 判断是否有环 快慢指针法
     * 
     * @param node
     * @return
     */
    public static boolean hasLoopV1(SingleNode headNode) {
        
        if(headNode == null) {
            return false;
        }
        
        SingleNode p = headNode;
        SingleNode q = headNode.next ;

        // 快指针未能遍历完所有节点
        while (q != null && q.next != null) {
            p = p.next; // 遍历一个节点
            q = q.next.next ; // 遍历两个个节点

            // 已到链表末尾
            if (q == null) {
                return false;
            } else if (p == q) {
                // 快慢指针相遇，存在环
                return true;
            }
        }

        return false;
    }
}

第二种：足迹法

思路：顺序遍历链表中所有的结点，并将其结点信息都保存下来。如果结点信息出现了两次，则存在环。

Java代码实现：

public class LinkADT<T> {

    /**
     * 单链表节点
     */
    private static class SingleNode<T> {
        public SingleNode<T> next;
        public T data;

        public SingleNode(T data) {
            this.data = data;
        }

        public T getNextNodeData() {
            return next != null ? next.data : null;
        }
    }

    // 保存足迹信息
    private static HashMap<SingleNode, Integer> nodeMap = new HashMap<>();

    /**
     * 判断是否有环 足迹法
     * 
     * @param node
     * @return
     */
    public static boolean hasLoopV2(SingleNode node, int index) {
        if (node == null || node.next == null) {
            return false;
        }

        if (nodeMap.containsKey(node)) {
            return true;
        } else {
            nodeMap.put(node, index);
            return hasLoopV2(node.next, ++index);
        }
    }
}