如何判读一个链表是不是有环链表？
暴力菜鸟版1
直接遍历这个链表，每进一个新结点就把这个节点和先前已经遍历的节点进行比较，如果新节点和之前遍历过得节点相同，那说明为有环节点，如果没有那么继续，直到尾节点也没有重复，那说明不是有环链表。
- 假设链表的节点数量为n，则该解法的时间复杂度为O(n 2 ) 。
- 由于并没 有创建额外的存储空间，所以空间复杂度为O(1) 。
暴力菜鸟版2
首先创建一个以节点ID为Key的HashSet集合，用来存储曾经遍历过的节点。然后同样从头节点开始，依次遍历单链表中的每一个节点。每遍历 一个新节点，都用新节点和HashSet集合中存储的节点进行比较，如果 发现HashSet中存在与之相同的节点ID，则说明链表有环，如果HashSet 中不存在与新节点相同的节点ID，就把这个新节点ID存入HashSet中， 之后进入下一节点，继续重复刚才的操作。
这个方法在流程上和方法1类似，本质的区别是使用了HashSet作为额外 的缓存。
- 假设链表的节点数量为n，则该解法的时间复杂度是O(n) 。
- 由于使用了 额外的存储空间，所以算法的空间复杂度同样是O(n) 。
进阶高手版
首先创建两个指针p1和p2（在Java里就是两个对象引用），让它们同时 指向这个链表的头节点。然后开始一个大循环，在循环体中，让指针p1 每次向后移动1个节点，让指针p2每次向后移动2个节点，然后比较两个 指针指向的节点是否相同。如果相同，则可以判断出链表有环，如果不同，则继续下一次循环
如果是有环链表就像是在环形跑道中，一个速度快一个速度慢，总会追上得，类似追及问题。
- 假设链表的节点数量为n，则该算法的时间复杂度为O(n)。
- 除两个指针外，没有使用任何额外的存储空间，所以空间复杂度是O(1)。
代码实现：
public static boolean isCycle(Node head){
Node p1 = head;
Node p2 = head;
while (p2!Null && p2.next != NULL) {
p1 = p1.next;
p2 = p2.next;
if (p1 = p2) {
return true;
}
}
return false;
}
private static class Node {
int data;
Node next;
Node(int data) {
this.data = data;
}
};
public static void main(String[] args) throws Exception {
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);
node1.next = node2;
node2.next = node3;
node3.next = node4;
node4.next = node5;
node5.next = node2;
System.out.println(isCycle(node1));
}# Python版代码实现
class Node:
def _init_(self,data):
self.data = data
self.next = none
def is_cycle(head):
p1 = head
p2 = head
while p2 is not None and p2,next is not None:
p1 = p1.next;
p2 = p2.next.next;
if p1 = p2:
return true;
return False
node1 = new Node(5);
node2 = new Node(3);
node3 = new Node(7);
node4 = new Node(2);
node5 = new Node(6);
node1.next = node2;
node2.next = node3;
node3.next = node4;
node4.next = node5;
node5.next = node2;
print(is_cycle(nodel))扩展问题1：如果链表有环，如何求出环的长度？
当两个指针首次相遇，证明链表有环的时候，让两个指针从相遇点继续循环前进，并统计前进的循环次数，直到两个指针第2次相遇。此时， 统计出来的前进次数就是环长。 因为指针p1每次走1步，指针p2每次走2步，两者的速度差是1步。当两 个指针再次相遇时，p2比p1多走了整整1圈。
因此，环长 = 每一次速度差 × 前进次数 = 前进次数。
扩展问题2： 如果链表有环，如何求出入环节点？
这个问题难一点点，但是耐心一点相信你能看懂的！
假设从链表头节点到入环点 的距离是D，
从入环点到两个指针首次相遇点的距离是S1 ，
从首次相遇点回到入环点的距离是S2。
那么，当两个指针首次相遇时，各自所走的距离是多少呢？
指针p1一次只走1步，所走的距离是D+S 1。
指针p2一次走2步，多走了n(n>=1)整圈，所走的距离是D+S1 +n(S1 +S1 )。
由于p2的速度是p1的2倍，所以所走距离也是p1的2倍，
因此： 2(D+S1 ) = D+S1+n(S1+S2 ) 等式
经过整理得出： D = (n-1)(S1+S2 )+S2 也就是说，从链表头结点到入环点的距离，等于从首次相遇点绕环n-1圈再回到入环点的距离。
这样一来，只要把其中一个指针放回到头节点位置，另一个指针保持在首次相遇点，两个指针都是每次向前走1步。那么，它们最终相遇的节点，就是入环节点。
本文来源自读书笔记：小灰的算法之旅,侵权必删。
