前天晚上临睡觉前看到了公众号脚本之家推送的一篇文章，文章内容是一道算法题，并给出了思路解释，但没有具体源码实现，这让我觉得少了点什么，于是，趁周末，我补齐了缺失的内容，好了，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.  1 //单向链表
  2.  2 public class SingleLinkedList {
  3.  3     private Node head;//标识头节点
  4.  4     private int size;//标识链表中节点个数
  5.  5     
  6.  6     public SingleLinkedList() {
  7.  7         this.size = 0;
  8.  8         this.head = null;
  9.  9     }
  10. 10     
  11. 11     //node类
  12. 12     private class Node{
  13. 13         private Object data;//每个节点的数据
  14. 14         private Node next;//指向下一个节点的链接
  15. 15         
  16. 16         public Node(Object data) {
  17. 17             this.data = data;
  18. 18         }
  19. 19     }
  20. 20     
  21. 21     /**
  22. 22      * 将节点插入链表
  23. 23      * @param data 带插入的值
  24. 24      */
  25. 25     public void add(Object data) {
  26. 26         Node temp = head;
  27. 27         if (size == 0) {
  28. 28             head = new Node(data);
  29. 29             size++;
  30. 30             return;
  31. 31         }
  32. 32         while (temp.next != null) {
  33. 33             temp = temp.next;
  34. 34         }
  35. 35         temp.next = new Node(data);
  36. 36         size++;
  37. 37     }
  38. 38     
  39. 39     /**
  40. 40      * 从头开始遍历节点
  41. 41      */
  42. 42     public void display() {
  43. 43         if (size > 0) {
  44. 44             Node node = head;
  45. 45             if (size == 1) {
  46. 46                 System.out.println("[" + node.data + "]");
  47. 47                 return;
  48. 48             }
  49. 49             while (node != null) {
  50. 50                 System.out.println(node.data);
  51. 51                 node = node.next;
  52. 52             }
  53. 53         } else {
  54. 54             System.out.println("[]");
  55. 55         }
  56. 56     }
  57. 57 }

View Code

方法1如下：

  1.  1     /**
  2.  2      * 根据索引得到链表的某个节点的值
  3.  3      * @param key
  4.  4      * @return
  5.  5      */
  6.  6     public Object getNode(int key) {
  7.  7         
  8.  8         if (key < 0 || key > size - 1) {
  9.  9             throw new ArrayIndexOutOfBoundsException("越界！");
  10. 10         } else {
  11. 11             Node temp = head;
  12. 12             int count = 0;
  13. 13             while (temp != null) {
  14. 14                 if (count == key) {
  15. 15                     return temp.data;
  16. 16                 }
  17. 17                 temp = temp.next;
  18. 18                 count++;
  19. 19             }
  20. 20             
  21. 21         }
  22. 22         return null;
  23. 23     }
  24. 24     
  25. 25     
  26. 26     /**
  27. 27      * 从头开始，依次与给定索引位置的节点的值进行比较，如果相同，则返回true，否则false
  28. 28      * @param key
  29. 29      * @return
  30. 30      */
  31. 31     public boolean havaSameElement(int key) {
  32. 32         boolean flag = false;
  33. 33         int count = 0;
  34. 34         Node temp = head;
  35. 35         while (temp != null && count < key) {
  36. 36             if (temp.data == getNode(key)) {
  37. 37                 flag = true;
  38. 38                 return flag;
  39. 39             }
  40. 40             count++;
  41. 41             temp = temp.next;
  42. 42         }
  43. 43         return flag;
  44. 44         
  45. 45     }
  46. 46     
  47. 47     /**
  48. 48      * 方式1
  49. 49      * @return
  50. 50      */
  51. 51     public boolean isAnnulate1() {
  52. 52         boolean flag = false;
  53. 53         for (int i = 1; i < size; i++) {
  54. 54             if (havaSameElement(i)) {
  55. 55                 flag = true;
  56. 56                 break;
  57. 57             }
  58. 58         }
  59. 59         return flag;
  60. 60     }

方法2：


这种方法用到了HashSet中add方法去重的特点，思路是这样的：

① new一个HashSet，用来存储之前遍历过的节点值

②从头节点head开始，依次遍历链表中的节点，并把它add到集合中

③ 如果在集合中已经有一个相同的值，那么会返回false，这样便证明链表有环，退出遍历

方法2如下：

  1.  1     /**
  2.  2      * 方式2
  3.  3      * @return
  4.  4      */
  5.  5     public boolean isAnnulate2() {
  6.  6         boolean flag = false;
  7.  7         Set<Object> set = new HashSet<>();
  8.  8         Node temp = head;
  9.  9         while (temp != null) {
  10. 10             if (!set.add(temp.data)) {
  11. 11                 flag = true;
  12. 12                 break;
  13. 13             }
  14. 14             temp = temp.next;
  15. 15         }
  16. 16         return flag;
  17. 17 
  18. 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.  1     public Node getIntersect() {
  2.  2         Node temp = head;
  3.  3         Node tortoise = temp;
  4.  4         Node rabbit = temp;
  5.  5         while (rabbit != null && rabbit.next != null) {
  6.  6             tortoise = tortoise.next;
  7.  7             rabbit = rabbit.next.next;
  8.  8             if (tortoise == rabbit) {
  9.  9                 return tortoise;
  10. 10             }
  11. 11         }
  12. 12         return null;
  13. 13     }
  14. 14     
  15. 15     public Object isAnnulate3() {
  16. 16         Node temp = head;
  17. 17         if (temp == null) {
  18. 18             return null;
  19. 19         }
  20. 20         Node intersect = getIntersect();
  21. 21         if (intersect == null) {
  22. 22             return null;
  23. 23         }
  24. 24         Node startNode = head;
  25. 25         while (startNode != intersect) {
  26. 26             startNode = startNode.next;
  27. 27             intersect = intersect.next;
  28. 28         }
  29. 29         return startNode.data;
  30. 30         
  31. 31     }

我要说明的是，方法3中的代码只是 “伪代码”，它并不能真的证明链表有环，并返回环的入口节点值。至于为什么，我的理解是，因为单链表的结构特点，它并不会真的存在 “环”，我们这里说的环只是把它抽象出来，实际上，单链表中一个节点只保留有对它后面那个节点的引用，并没有对它前面节点的引用，所以，并不存在真正的 “环”，不过，这种思路还是值得学习的。假设链表的节点数量为n，则该算法的时间复杂度为O（n），除指针外，没有占用任何额外的存储空间，所以空间复杂度为O（1）。

完整代码如下：

  1.   1 package judgeLinkedListCircle;
  2.   2 
  3.   3 import java.util.HashSet;
  4.   4 import java.util.Set;
  5.   5 
  6.   6 
  7.   7 /**
  8.   8  * 单向链表
  9.   9  * @author Cone
  10.  10  * @since 2019年7月27日
  11.  11  *
  12.  12  */
  13.  13 public class SingleLinkedList {
  14.  14     private Node head;//标识头节点
  15.  15     private int size;//标识链表中节点个数
  16.  16     
  17.  17     public SingleLinkedList() {
  18.  18         this.size = 0;
  19.  19         this.head = null;
  20.  20     }
  21.  21     
  22.  22     //node类
  23.  23     private class Node{
  24.  24         private Object data;//每个节点的数据
  25.  25         private Node next;//指向下一个节点的链接
  26.  26         
  27.  27         public Node(Object data) {
  28.  28             this.data = data;
  29.  29         }
  30.  30     }
  31.  31     
  32.  32     /**
  33.  33      * 将节点插入链表
  34.  34      * @param data 带插入的值
  35.  35      */
  36.  36     public void add(Object data) {
  37.  37         Node temp = head;
  38.  38         if (size == 0) {
  39.  39             head = new Node(data);
  40.  40             size++;
  41.  41             return;
  42.  42         }
  43.  43         while (temp.next != null) {
  44.  44             temp = temp.next;
  45.  45         }
  46.  46         temp.next = new Node(data);
  47.  47         size++;
  48.  48     }
  49.  49     
  50.  50     /**
  51.  51      * 从头开始遍历节点
  52.  52      */
  53.  53     public void display() {
  54.  54         if (size > 0) {
  55.  55             Node node = head;
  56.  56             if (size == 1) {
  57.  57                 System.out.println("[" + node.data + "]");
  58.  58                 return;
  59.  59             }
  60.  60             while (node != null) {
  61.  61                 System.out.println(node.data);
  62.  62                 node = node.next;
  63.  63             }
  64.  64         } else {
  65.  65             System.out.println("[]");
  66.  66         }
  67.  67     }
  68.  68     
  69.  69     /**
  70.  70      * 根据索引得到链表的某个节点的值
  71.  71      * @param key
  72.  72      * @return
  73.  73      */
  74.  74     public Object getNode(int key) {
  75.  75         
  76.  76         if (key < 0 || key > size - 1) {
  77.  77             throw new ArrayIndexOutOfBoundsException("越界！");
  78.  78         } else {
  79.  79             Node temp = head;
  80.  80             int count = 0;
  81.  81             while (temp != null) {
  82.  82                 if (count == key) {
  83.  83                     return temp.data;
  84.  84                 }
  85.  85                 temp = temp.next;
  86.  86                 count++;
  87.  87             }
  88.  88             
  89.  89         }
  90.  90         return null;
  91.  91     }
  92.  92     
  93.  93     
  94.  94     /**
  95.  95      * 从头开始，依次与给定索引位置的节点的值进行比较，如果相同，则返回true，否则false
  96.  96      * @param key
  97.  97      * @return
  98.  98      */
  99.  99     public boolean havaSameElement(int key) {
  100. 100         boolean flag = false;
  101. 101         int count = 0;
  102. 102         Node temp = head;
  103. 103         while (temp != null && count < key) {
  104. 104             if (temp.data == getNode(key)) {
  105. 105                 flag = true;
  106. 106                 return flag;
  107. 107             }
  108. 108             count++;
  109. 109             temp = temp.next;
  110. 110         }
  111. 111         return flag;
  112. 112         
  113. 113     }
  114. 114     
  115. 115     /**
  116. 116      * 方式1
  117. 117      * @return
  118. 118      */
  119. 119     public boolean isAnnulate1() {
  120. 120         boolean flag = false;
  121. 121         for (int i = 1; i < size; i++) {
  122. 122             if (havaSameElement(i)) {
  123. 123                 flag = true;
  124. 124                 break;
  125. 125             }
  126. 126         }
  127. 127         return flag;
  128. 128     }
  129. 129     
  130. 130     
  131. 131     /**
  132. 132      * 方式2
  133. 133      * @return
  134. 134      */
  135. 135     public boolean isAnnulate2() {
  136. 136         boolean flag = false;
  137. 137         Set<Object> set = new HashSet<>();
  138. 138         Node temp = head;
  139. 139         while (temp != null) {
  140. 140             if (!set.add(temp.data)) {
  141. 141                 flag = true;
  142. 142                 break;
  143. 143             }
  144. 144             temp = temp.next;
  145. 145         }
  146. 146         return flag;
  147. 147 
  148. 148     }
  149. 149     
  150. 150     public Node getIntersect() {
  151. 151         Node temp = head;
  152. 152         Node tortoise = temp;
  153. 153         Node rabbit = temp;
  154. 154         while (rabbit != null && rabbit.next != null) {
  155. 155             tortoise = tortoise.next;
  156. 156             rabbit = rabbit.next.next;
  157. 157             if (tortoise == rabbit) {
  158. 158                 return tortoise;
  159. 159             }
  160. 160         }
  161. 161         return null;
  162. 162     }
  163. 163     
  164. 164     /**
  165. 165      * 方式3
  166. 166      * @return
  167. 167      */
  168. 168     public Object isAnnulate3() {
  169. 169         Node temp = head;
  170. 170         if (temp == null) {
  171. 171             return null;
  172. 172         }
  173. 173         Node intersect = getIntersect();
  174. 174         if (intersect == null) {
  175. 175             return null;
  176. 176         }
  177. 177         Node startNode = head;
  178. 178         while (startNode != intersect) {
  179. 179             startNode = startNode.next;
  180. 180             intersect = intersect.next;
  181. 181         }
  182. 182         return startNode.data;
  183. 183         
  184. 184     }
  185. 185 
  186. 186 }

View Code

如有错误，欢迎指正。

代码已上传至github：

https://github.com/Thinker-Mars/ByteDance

 

版权声明：本文为cone原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://www.cnblogs.com/cone/p/11257063.html