判断单链表有环

双指针

穷举遍历

哈希表缓存

快慢指针

p1, p2指针从头开始扫描链表。指针p1每次走1步，指针p2每次走2步。
如果存在环，则指针p1、p2会相遇；如果不存在环，指针fast遇到NULL退出。

步骤演示：

ref: https://blog.csdn.net/mucaoyx/article/details/81395782

原理分析：

Q1: 求入环点。

Q2: 求环的长度。

求环长：
从首次相遇节点继续循环前进，直到两个指针第2次相遇。
此时，统计出来的前进次数就是环长。

求入环点：
首次相遇时，
指针p1每次只走一步，走过的距离 D+S1
指针p2每次走两步，比p1多走一圈，做过的距离 D + S1 + S2 + S1
p2的速度是p1的两倍，p2走过的距离也是p1的两倍，
===> 2(D+S1) = D + 2S1 + S2
===> D = S2

只要把其中一个指针放回到头节点位置，另一个指针在首次相遇的节点，两个指针每次向前走一步，
最终归相遇的节点，就是入环节点。

public class Node {
	int data;
	Node next;

	public Node(int data) {
		this.data = data;
	}
}

public class TestLinked {

	public boolean isCycle(Node head) {
		if (head.next == null) {
			return false;
		}
		return getSameNode(head) != null;
	}

	public Integer getLengthOfCycle(Node head) {
		if (!isCycle(head)) {
			return 0;
		}
		Node slowNode = getSameNode(head);
		Node first = slowNode.next;
		Node second = slowNode.next.next;
		int i = 1;
		while (first != second) {
			i++;
			first = first.next;
			second = second.next.next;
		}
		return i;
	}

	private Node getSameNode(Node node) {
		Node fastNode = node;
		Node slowNode = node;
		while (fastNode != null) {
			if (fastNode.next != null) {
				fastNode = fastNode.next.next;
			} else {
				fastNode = null;
			}
			slowNode = slowNode.next;
			if (slowNode == fastNode) {
				return slowNode;
			}
		}
		return null;
	}

	public Node getEntranceOfCycle(Node head) {
		Node fastNode = head;
		Node slowNode = head;
		while (fastNode != null) {
			if (fastNode.next != null) {
				fastNode = fastNode.next.next;
			} else {
				fastNode = null;
			}
			slowNode = slowNode.next;
			if (slowNode == fastNode) {
				fastNode = head;
				while (fastNode != slowNode) {
					fastNode = fastNode.next;
					slowNode = slowNode.next;
				}
				return slowNode;
			}
		}
		return null;
	}

	@Test
	public void testIsCycle() {
		System.out.println(isCycle(Util.createList()));
	}

	@Test
	public void testGetLengthOfCycle() {
		System.out.println(getLengthOfCycle(Util.createList()));
	}

	@Test
	public void testGetEntranceOfCycle() {
		System.out.println(getEntranceOfCycle(Util.createList()).data);
	}

}

public class Util {

	public static Node createList() {
		Node node1 = new Node(5);
		Node node2 = new Node(3);
		Node node3 = new Node(7);
		Node node4 = new Node(2);
		Node node5 = new Node(6);
		Node node6 = new Node(8);
		Node node7 = new Node(1);
		node1.next = node2;
		node2.next = node3;
		node3.next = node4;
		node4.next = node5;
		node5.next = node6;
		node6.next = node7;
		node7.next = node4;
		return node1;
	}
}

参考文章