如何判断链表有环
如何判断链表有环
前天晚上临睡觉前看到了公众号脚本之家推送的一篇文章，文章内容是一道算法题，并给出了思路解释，但没有具体源码实现，这让我觉得少了点什么，于是，趁周末，我补齐了缺失的内容，好了，no code, no bb，我们开始吧。
题目描述：
有一个单向链表，链表中有可能出现“环”，就像下图这样。那么，如何用程序来判断该链表是否为有环链表呢？（图片来自公众号）
方法1：
从头开始遍历整个单链表，每遍历一个新节点，就把它与之前遍历过的节点进行比较，如果值相同，那么就认为这两个节点是一个节点，则证明链表有环，停止遍历，否则继续遍历下一个节点，重复刚才的操作，直到遍历结束。结合上图来说，流程是这样的：
① 得到 “3”节点，把它与第一个节点 “5”比较，值不相等，继续遍历下一个节点 “7”。（从第二个节点开始遍历）
② 得到 “7”节点，把它依次与 “5”、“3”比较，值不相等，继续遍历下一个节点 “2”
③ 重复以上操作，直到遍历完节点 “1”
④ 得到节点 “2”，把它依次与 “5”、“3”、“7”、“2”、“6”、“8”、“1”进行比较，当比较到节点 “2”时，值相等，遍历结束，证明该链表有环。
假设链表的节点数量为n，则该解法的时间复杂度为O（n2），由于没有创建额外的存储空间，所以空间复杂度为O（1）
链表的实现比较简单，我只写了一个add方法，一个display方法：
1 //单向链表 2 public class SingleLinkedList { 3 private Node head;//标识头节点 4 private int size;//标识链表中节点个数 5 6 public SingleLinkedList() { 7 this.size = 0; 8 this.head = null; 9 } 10 11 //node类 12 private class Node{ 13 private Object data;//每个节点的数据 14 private Node next;//指向下一个节点的链接 15 16 public Node(Object data) { 17 this.data = data; 18 } 19 } 20 21 /** 22 * 将节点插入链表 23 * @param data 带插入的值 24 */ 25 public void add(Object data) { 26 Node temp = head; 27 if (size == 0) { 28 head = new Node(data); 29 size++; 30 return; 31 } 32 while (temp.next != null) { 33 temp = temp.next; 34 } 35 temp.next = new Node(data); 36 size++; 37 } 38 39 /** 40 * 从头开始遍历节点 41 */ 42 public void display() { 43 if (size > 0) { 44 Node node = head; 45 if (size == 1) { 46 System.out.println("[" + node.data + "]"); 47 return; 48 } 49 while (node != null) { 50 System.out.println(node.data); 51 node = node.next; 52 } 53 } else { 54 System.out.println("[]"); 55 } 56 } 57 }
View Code
方法1如下：
1 /** 2 * 根据索引得到链表的某个节点的值 3 * @param key 4 * @return 5 */ 6 public Object getNode(int key) { 7 8 if (key < 0 || key > size - 1) { 9 throw new ArrayIndexOutOfBoundsException("越界！"); 10 } else { 11 Node temp = head; 12 int count = 0; 13 while (temp != null) { 14 if (count == key) { 15 return temp.data; 16 } 17 temp = temp.next; 18 count++; 19 } 20 21 } 22 return null; 23 } 24 25 26 /** 27 * 从头开始，依次与给定索引位置的节点的值进行比较，如果相同，则返回true，否则false 28 * @param key 29 * @return 30 */ 31 public boolean havaSameElement(int key) { 32 boolean flag = false; 33 int count = 0; 34 Node temp = head; 35 while (temp != null && count < key) { 36 if (temp.data == getNode(key)) { 37 flag = true; 38 return flag; 39 } 40 count++; 41 temp = temp.next; 42 } 43 return flag; 44 45 } 46 47 /** 48 * 方式1 49 * @return 50 */ 51 public boolean isAnnulate1() { 52 boolean flag = false; 53 for (int i = 1; i < size; i++) { 54 if (havaSameElement(i)) { 55 flag = true; 56 break; 57 } 58 } 59 return flag; 60 }
方法2：
这种方法用到了HashSet中add方法去重的特点，思路是这样的：
① new一个HashSet，用来存储之前遍历过的节点值
②从头节点head开始，依次遍历链表中的节点，并把它add到集合中
③ 如果在集合中已经有一个相同的值，那么会返回false，这样便证明链表有环，退出遍历
方法2如下：
1 /** 2 * 方式2 3 * @return 4 */ 5 public boolean isAnnulate2() { 6 boolean flag = false; 7 Set<Object> set = new HashSet<>(); 8 Node temp = head; 9 while (temp != null) { 10 if (!set.add(temp.data)) { 11 flag = true; 12 break; 13 } 14 temp = temp.next; 15 } 16 return flag; 17 18 }
方法3：
定义两个指针tortoise与rabbit，让它们一开始均指向head头节点，之后，tortoise每次向后移动一个节点，rabbit每次向后移动2个节点，只要这个链表是有环的，它们必定会在某一次移动完后相遇，什么？你问我为什么？我们来思考这样一个问题，两个人在运动场跑步，他们的起始位置都是一样的，当开跑后，只有在两种情况下，他们的位置会重合，第一就是他们的速度始终一致，第二就是跑得快的那个人套圈，如下图所示：
我们假设两位跑步的同学速度始终不变，即tortoise以V的速度进行移动，rabbit以2V的速度进行移动，在经过了相同的时间T后，他们相遇了，此时tortoise移动的距离为VT，而rabbit移动的距离为2VT，他们移动的距离差VT，即为这个链表中 “环”的周长，如上图所示，节点A表示为环入口，节点B表示他们第一次相遇，我们将head头节点至节点A的距离记为a，将节点A至他们第一次相遇的节点B的距离记为b，通过我们刚才的分析，不难得出，tortoise移动的距离VT = a + b，等量代换，他们移动的距离差也为 a+ b，所以链表中环的周长为 a + b，现在已知节点A至节点B的距离为b，那么节点B至节点A的距离便为a，至此，发现什么了？head头节点到节点A的距离同样为a，我们建立一个指针 start 指向头节点，它与B节点处的tortoise同时以一个节点的速度进行移动，一段时间后，它们将在环入口相遇。我们不光能证明一个链表是否有环，还能找到环的入口。
方法3如下：
1 public Node getIntersect() { 2 Node temp = head; 3 Node tortoise = temp; 4 Node rabbit = temp; 5 while (rabbit != null && rabbit.next != null) { 6 tortoise = tortoise.next; 7 rabbit = rabbit.next.next; 8 if (tortoise == rabbit) { 9 return tortoise; 10 } 11 } 12 return null; 13 } 14 15 public Object isAnnulate3() { 16 Node temp = head; 17 if (temp == null) { 18 return null; 19 } 20 Node intersect = getIntersect(); 21 if (intersect == null) { 22 return null; 23 } 24 Node startNode = head; 25 while (startNode != intersect) { 26 startNode = startNode.next; 27 intersect = intersect.next; 28 } 29 return startNode.data; 30 31 }
我要说明的是，方法3中的代码只是 “伪代码”，它并不能真的证明链表有环，并返回环的入口节点值。至于为什么，我的理解是，因为单链表的结构特点，它并不会真的存在 “环”，我们这里说的环只是把它抽象出来，实际上，单链表中一个节点只保留有对它后面那个节点的引用，并没有对它前面节点的引用，所以，并不存在真正的 “环”，不过，这种思路还是值得学习的。假设链表的节点数量为n，则该算法的时间复杂度为O（n），除指针外，没有占用任何额外的存储空间，所以空间复杂度为O（1）。
完整代码如下：
1 package judgeLinkedListCircle; 2 3 import java.util.HashSet; 4 import java.util.Set; 5 6 7 /** 8 * 单向链表 9 * @author Cone 10 * @since 2019年7月27日 11 * 12 */ 13 public class SingleLinkedList { 14 private Node head;//标识头节点 15 private int size;//标识链表中节点个数 16 17 public SingleLinkedList() { 18 this.size = 0; 19 this.head = null; 20 } 21 22 //node类 23 private class Node{ 24 private Object data;//每个节点的数据 25 private Node next;//指向下一个节点的链接 26 27 public Node(Object data) { 28 this.data = data; 29 } 30 } 31 32 /** 33 * 将节点插入链表 34 * @param data 带插入的值 35 */ 36 public void add(Object data) { 37 Node temp = head; 38 if (size == 0) { 39 head = new Node(data); 40 size++; 41 return; 42 } 43 while (temp.next != null) { 44 temp = temp.next; 45 } 46 temp.next = new Node(data); 47 size++; 48 } 49 50 /** 51 * 从头开始遍历节点 52 */ 53 public void display() { 54 if (size > 0) { 55 Node node = head; 56 if (size == 1) { 57 System.out.println("[" + node.data + "]"); 58 return; 59 } 60 while (node != null) { 61 System.out.println(node.data); 62 node = node.next; 63 } 64 } else { 65 System.out.println("[]"); 66 } 67 } 68 69 /** 70 * 根据索引得到链表的某个节点的值 71 * @param key 72 * @return 73 */ 74 public Object getNode(int key) { 75 76 if (key < 0 || key > size - 1) { 77 throw new ArrayIndexOutOfBoundsException("越界！"); 78 } else { 79 Node temp = head; 80 int count = 0; 81 while (temp != null) { 82 if (count == key) { 83 return temp.data; 84 } 85 temp = temp.next; 86 count++; 87 } 88 89 } 90 return null; 91 } 92 93 94 /** 95 * 从头开始，依次与给定索引位置的节点的值进行比较，如果相同，则返回true，否则false 96 * @param key 97 * @return 98 */ 99 public boolean havaSameElement(int key) { 100 boolean flag = false; 101 int count = 0; 102 Node temp = head; 103 while (temp != null && count < key) { 104 if (temp.data == getNode(key)) { 105 flag = true; 106 return flag; 107 } 108 count++; 109 temp = temp.next; 110 } 111 return flag; 112 113 } 114 115 /** 116 * 方式1 117 * @return 118 */ 119 public boolean isAnnulate1() { 120 boolean flag = false; 121 for (int i = 1; i < size; i++) { 122 if (havaSameElement(i)) { 123 flag = true; 124 break; 125 } 126 } 127 return flag; 128 } 129 130 131 /** 132 * 方式2 133 * @return 134 */ 135 public boolean isAnnulate2() { 136 boolean flag = false; 137 Set<Object> set = new HashSet<>(); 138 Node temp = head; 139 while (temp != null) { 140 if (!set.add(temp.data)) { 141 flag = true; 142 break; 143 } 144 temp = temp.next; 145 } 146 return flag; 147 148 } 149 150 public Node getIntersect() { 151 Node temp = head; 152 Node tortoise = temp; 153 Node rabbit = temp; 154 while (rabbit != null && rabbit.next != null) { 155 tortoise = tortoise.next; 156 rabbit = rabbit.next.next; 157 if (tortoise == rabbit) { 158 return tortoise; 159 } 160 } 161 return null; 162 } 163 164 /** 165 * 方式3 166 * @return 167 */ 168 public Object isAnnulate3() { 169 Node temp = head; 170 if (temp == null) { 171 return null; 172 } 173 Node intersect = getIntersect(); 174 if (intersect == null) { 175 return null; 176 } 177 Node startNode = head; 178 while (startNode != intersect) { 179 startNode = startNode.next; 180 intersect = intersect.next; 181 } 182 return startNode.data; 183 184 } 185 186 }
View Code
如有错误，欢迎指正。
代码已上传至github：