链表中与环相关的问题

这里主要总结面试中有关链表中环的问题，以后遇到同类型题目会扩充内容

如何判断链表是否有环

1. 穷举遍历

首先从头节点开始，依次遍历单链表的每一个节点。每遍历到一个新节点，就从头节点重新遍历新节点之前的所有节点，用新节点ID和此节点之前所有节点ID依次作比较。如果发现新节点之前的所有节点当中存在相同节点ID，则说明该节点被遍历过两次，链表有环；如果之前的所有节点当中不存在相同的节点，就继续遍历下一个新节点，继续重复刚才的操作
假设从链表头节点到入环点的距离是D，链表的环长是S。那么算法的时间复杂度是$0+1+2+3+…+(D+S-1) = {\frac{(D+S-1)(D+S)}{2}}$ , 即$O(n^2)$。而此算法没有创建额外存储空间，则空间复杂度为$O(1)$

2. 哈希缓存

首先创建一个以节点ID为键的HashSet集合，用来存储曾经遍历过的节点。然后同样是从头节点开始，依次遍历单链表的每一个节点。每遍历到一个新节点，就用新节点和HashSet集合当中存储的节点作比较，如果发现HashSet当中存在相同节点ID，则说明链表有环，如果HashSet当中不存在相同的节点ID，就把这个新节点ID存入HashSet，之后进入下一节点，继续重复刚才的操作
假设从链表头节点到入环点的距离是D，链表的环长是S。而每一次HashSet查找元素的时间复杂度是$O(1)$, 所以总体的时间复杂度是$O(D+S)$，即$O(n)$。而算法的空间复杂度还是$O(D+S-1)$，即$O(n)$

3. 快慢指针

首先创建两个指针1和2（在java里就是两个对象引用），同时指向这个链表的头节点。然后开始一个大循环，在循环体中，让指针1每次向下移动一个节点，让指针2每次向下移动两个节点，然后比较两个指针指向的节点是否相同。如果相同，则判断出链表有环，如果不同，则继续下一次循环

借鉴了数学中的追击问题，原理就是：在一个环形跑道上，两个运动员在同一地点起跑，一个运动员速度快，一个运动员速度慢。当两人跑了一段时间，速度快的运动员必然会从速度慢的运动员身后再次追上并超过，原因很简单，因为跑道是环形的

假设从链表头节点到入环点的距离是D，链表的环长是S。那么循环会进行S次，时间复杂度即为$O(n)$。除了两个指针以外，没有使用任何额外存储空间，所以空间复杂度是$O(1)$

代码如下：

public class AboutCycle {private static class Node{int data;Node next;Node(int data){this.data = data;}}/*** 快慢指针实现* @param head 待判断的链表* @return true if has cycle otherwise false*/public static boolean isCycle(Node head){Node p1 = head;Node p2 = head;while (p2!=null && p2.next!=null){p1 = p1.next;p2 = p2.next.next;if (p1 == p2){return true;}}return false;}public static void main(String[] args) {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 = null;node7.next = node4;System.out.println(isCycle(node1));}
}

如果链表有环，求环长度

1. 在指针slow和fast相遇后，让其中一个继续向前走，下次相遇时，所经过的结点，就是环上的结点个数

2. 在指针slow和fast相遇后，让slow和fast同时继续向前走，下次相遇时，所经过的结点，就是环上的结点个数

如果链表有环，求入环节点

假设从链表头节点到入环节点的距离是D，从入环到两个指针首次相遇点的距离是$S_1$，从首次相遇回到入环点的距离是$S_2$。当两个指针首次相遇时，慢指针所走距离是$D+S_1$，快指针1次走2步，多走1整圈，因此距离是$D+2S_1+S_2$，根据公式：
$2*(D+S_1)=D+2S_1+S_2$
得到：$D=S_2$
也就是说，是要把其中一个指针放回到头节点位置，另一个节点保持在首次相遇点，两个指针都每次向前走一步，那么它们最终相遇的节点就是入环节点

如果链表有环，求链表节点个数

链表长度L = 起点到入口点的距离D + 环的长度R
在前面的基础上可以轻松求出

判断两个无环链表是否相交

如图所示，存在两个无环相交链表，我们只需要将链表1的首尾相连，这样就变成我们熟悉的判断是否有环的问题了！

参考链接

1. 《漫画算法-小灰的算法之旅》