題目地址：https://leetcode-cn.com/problems/linked-list-cycle/
題目：
給定一個鏈表，判斷鏈表中是否有環(huán)。
進階：你能否不使用額外空間解決此題？
試題分析：
查看鏈表是否有環(huán)主要有兩個方法比較，
一種是利用set數(shù)據結構，set是一種不會有重復數(shù)據的集合結構，遍歷鏈表，將鏈表的節(jié)點依次放入set中，如果遍歷的節(jié)點在set中還沒有則add到set中，如果已經存在則說明鏈表有重復節(jié)點有環(huán)。
還有一種方法是比較特殊的算法，快慢指針法，這種算法比較詭異，一般人不容易想到，核心思路就是定義兩個指針，一個快指針、一個慢指針，慢指針每次只移動一個節(jié)點，快指針每次移動兩個節(jié)點，如果整個鏈表中有環(huán)，那么快慢指針一定會相遇，不相信的話，可以自己在草稿紙上分步畫下就會發(fā)現(xiàn)如果有環(huán)一定會相遇。
代碼：
<pre class="md-fences md-end-block" lang="java" contenteditable="false" cid="n89" mdtype="fences" style="box-sizing: border-box; overflow: visible; font-family: Consolas, "Liberation Mono", Courier, monospace; font-size: 0.9em; white-space: pre; text-align: left; break-inside: avoid; display: block; background-image: inherit; background-size: inherit; background-attachment: inherit; background-origin: inherit; background-clip: inherit; background-color: rgb(248, 248, 248); position: relative !important; border: 1px solid rgb(221, 221, 221); border-top-left-radius: 3px; border-top-right-radius: 3px; border-bottom-right-radius: 3px; border-bottom-left-radius: 3px; padding: 8px 1em 6px; margin-bottom: 15px; margin-top: 15px; width: inherit; caret-color: rgb(51, 51, 51); color: rgb(51, 51, 51); font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-indent: 0px; text-transform: none; widows: auto; word-spacing: 0px; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px; text-decoration: none; background-position: inherit inherit; background-repeat: inherit inherit;"> public boolean hasCycle(ListNode head) {
HashSet<ListNode> set = new HashSet<ListNode>();
while(head!=null){
if(set.contains(head)){
return true;
}else{
set.add(head);
head = head.next;
}
}
return false;
}
?
public boolean hasCycle2(ListNode head) {
//快慢指針方法，快指針比慢指針每次快兩倍
ListNode slow =head;
ListNode fast = head;
while(slow!=null && fast!=null && fast.next!=null){
slow = slow.next;
fast = fast.next.next;
if(slow==fast){
return true;
}
}
return false;
}</pre>
源碼路徑：com.monkey01.linkedlist.LinkedListCycle_141
配套測試代碼路徑：test目錄com.monkey01.linkedlist.LinkedListCycle_141Test
