快慢指針

算法描寫敘述

定義兩個指針slow, fast。

slow指針一次走1個結點，fast指針一次走2個結點。假設鏈表中有環，那么慢指針一定會再某一個時刻追上快指針(slow == fast)。假設沒有環，則快指針會第一個走到NULL。

實現

結點定義例如以下：

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

算法：

/*** 快慢指針* @param head* @return*/public static boolean checkCircle(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*/public static int findCircleEntry(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;}

總結

以上是生活随笔為你收集整理的推断单向链表中是否有环和查找环的入口的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。