判断单向链表中是否有环和查找环的入口

分类：算法

链表算法

快慢指针算法描述

定义两个指针slow, fast。slow指针一次走1个结点，fast指针一次走2个结点。如果链表中有环，那么慢指针一定会再某一个时刻追上快指针(slow == fast)。如果没有环，则快指针会第一个走到NULL。

实现

结点定义如下：

class Node {public Node next;public Object data;sequence = 0;}

算法：

/*** 快慢指针* @param head* @return*/(Node head) {Node fast = null;Node slow = null;fast = head;slow = head;while (true) {// 慢指针移动一步if (null != slow.next) {slow = slow.next;} else {return false;}// 快指针移动两步if (null != fast.next && null != fast.next.next) {fast = fast.next.next;} else {return false;}// 检查是否相遇if (slow == fast) {return true;}}}步数检查算法描述

上面的算法只能判断链表中有没有环，如果我们想找出环的入口怎么办呢？

定义两个指针p, q。p每走一个结点(即一步)，q则从头一直向后走，直到q走到NULL或p, q走到同一个结点但走过的步数不相同为止。此时q的步数就是环入口在结点中的位置。如果走到NULL则说明链表不存在环。

为什么p, q走到同一个结点但步数不相等时就说明有环呢？因为如果p, q步数相同，说明它们走过的结点是一样的，如果p, q步数不同了，则说明p是从环里走了一圈又回到了环的入口，此时q到达该结点时还没有走过环，因此步数不相等，而且此时q的步数就是环的入口。

实现/*** 查找环的起点* @param head* @return 返回元素的索引，从0开始。没有找到返回-1*/(Node head) {Node p = head; // 总是从头开始Node q = head;int pSteps = 0;int qSteps = 0;while (null != q.next) {q = q.next;++qSteps;// p从头开始走while (null != p.next) {p = p.next;++pSteps;// 当p与q指向同一个结点时if (p == q) {// 如果走的步数不同，，则这就是入口if (pSteps != qSteps) {return pSteps – 1;} else {// 走的步数相同，不是入口break;}}}p = head; // 回到头结点pSteps = 0;}// 其中有一个指针走到了头，说明没有环return -1;}

上一篇Linux下Tomcat VM参数修改

顶0踩0

世上再美的风景，都不及回家的那段路。

相关文章：

你感兴趣的文章：

标签云：