快慢指针判断链表是否有环

快慢指针判断链表是否有环

单链表有可能存在环，有些情况下要判断一个单链表是否有环。数组的有个快慢指针的方法，其实单链表和数组有相似的地方，可以使用快慢指针的方法。具体做法如下：

首先创建两个指针，它们初始时指向链表的头部。然后令一个指针一次移动一个节点，另外一个指针一次移动两个节点。然后比较两个指针指向的节点是否相同。如果相同，则判断出链表有环，如果不同，则继续进行。

代码如下：

     /*** 根据索引得到链表的某个节点的值* @param key* @return*/public Object getNode(int key) {if (key < 0 || key > size - 1) {throw new ArrayIndexOutOfBoundsException("越界！");} else {Node temp = head;int count = 0;while (temp != null) {if (count == key) {return temp.data;}temp = temp.next;count++;}}return null;}/*** 从头开始，依次与给定索引位置的节点的值进行比较，如果相同，则返回true，否则false* @param key* @return*/public boolean havaSameElement(int key) {boolean flag = false;int count = 0;Node temp = head;while (temp != null && count < key) {if (temp.data == getNode(key)) {flag = true;return flag;}count++;temp = temp.next;}return flag;}/*** 方式1* @return*/public boolean isAnnulate1() {boolean flag = false;for (int i = 1; i < size; i++) {if (havaSameElement(i)) {flag = true;break;}}return flag;}

很简单的思路是把原始链表转化为一条反转链表，然后比较这两条链表是否是一样的。因为链表没法使用双指针的方法。

另一种比较难的方法是使用二叉树的后序遍历的思路，不需要明显的使用反转链表也可以倒序遍历链表，下面来具体讨论这个问题：

二叉树的遍历操作也是递归算法。

该文章会更新，欢迎大家批评指正。

推荐一个零声学院免费公开课程，个人觉得老师讲得不错，
分享给大家：[Linux，Nginx，ZeroMQ，MySQL，Redis，
fastdfs，MongoDB，ZK，流媒体，CDN，P2P，K8S，Docker，
TCP/IP，协程，DPDK等技术内容，点击立即学习:
服务器课程：C++服务器